Questions tagged [computational-complexity]

Use for questions about the efficiency of a specific algorithm (the amount of resources, such as running time or memory, that it requires) or for questions about the efficiency of any algorithm solving a given problem.

Filter by
Sorted by
Tagged with
0
votes
1answer
22 views

Prove decidability or undecidability of a language accepted by a turing machine.

consider this problem: "Given a TM $X$, determine if the language accepted by $X$ contains more than $100$ strings" Is this problem decidable or not? Opinion 1: (mine) I derived my proof by ...
2
votes
3answers
59 views

What is the best computational software(free/cheap)? [closed]

I have already tried Wolfram Alpha (not pro) and I don't know whether I can access MATLAB for free, any software than downloaded for free and is easy to use will work. I need it for computing complex ...
-1
votes
0answers
66 views

Can anyone help me verify if this prime sieve is going to work ? Also, can anyone help me determine whether this has high computational efficiency?

Here's a link to my conjecture : Quora - My New Prime Number Sieve Here's the content: A New Prime Sieve ! Hello there ! I think I’ve found a way to find prime numbers ! (Not a function, but a ...
0
votes
0answers
30 views

Freshman's dream over multivariate polynomial rings

I'm working on a project where I am trying to manipulate vandermonde matricies with entries that are monomials $M_t \in \mathbb{F}[x_1,\dots x_n]$. I am trying to equate this with another vandermonde ...
2
votes
0answers
38 views

Recursion for Characteristic Polynomial - Proof?

In the book "Computational Complexity of Counting and Sampling" I have found the following theorem: It gives a recursion formula for a division-free algorithm for the determinant in $O(n^4)$...
0
votes
1answer
29 views

Find the longest subinterval of [0,1] with a finite number of queries

We have a number of intervals (either finite or infinite), not overlapping if not for their extreme points, which union is [0,1]. One of them is long at least 1/4, and all the others are not longer ...
0
votes
0answers
13 views

algebraic branching programs and the 3x3 permanent

Using Grenet's construction (http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=193FC514DC541C17E8F03A7A6BDE4C61?doi=10.1.1.717.4014&rep=rep1&type=pdf ) we can write the 3x3 permanent as ...
-1
votes
0answers
29 views

Is mathematical proof itself NP-hard? [closed]

At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to ...
0
votes
1answer
15 views

pentadiagonal matrix vector multiplication

I have a pentadiagonal symmetric matrix , with elements on the diagonal, on the 1st upper-diagonal and 1st lower-diagonal and at the n-th upper and lower diagonal. ( n changes values from one matrix ...
2
votes
1answer
32 views

Computational complexity of a modified Euclidean algorithm

The Euclidean algorithm computes the $\gcd$ of two integers with the recursive formula $$\gcd(a,b)=\gcd(b,a\bmod b)$$ and takes at worst $\log_\varphi(\min(a,b))$ steps, where $\varphi$ is the golden ...
0
votes
0answers
18 views

Understanding the protocol of Hsiao-Ying Lin and Wen-Guey Tzeng

I am trying to understand the solution proposed by Hsiao-Ying Lin and Wen-Guey Tzeng to Yao's Millionaires' Problem. Correct me guys if I am wrong but from what I have understood so far from the two ...
0
votes
0answers
15 views

Order to bound Taylor expansion error: not as straightforward as it seems.

Suppose we have the function $f(x) = e^{x}$, and we choose $0<x/r<1$. The Taylor expansion is $$ f(x/r) = \sum_{k=0}^\infty \frac{(x/r)^k}{k!}. $$ If we truncate the series at order $K$ then the ...
0
votes
1answer
36 views

overall complexity of an algorithm

Is the following way of thinking correct? Assume one has some Algorithm, which for some fixed integer $n$ and some $i = 1,\dots, k$ has computational complexity $O(i\times n^{2})$. Assume I have to ...
1
vote
0answers
21 views

the centroid-based clustering is NP-hard

I am trying to understand why the centroid-based clustering is NP-hard. Assume we have one-dimensional sorted data set $x_{1}, \dots, x_{n}$ and we want to find, say $k$, optimal clusters (intervals) $...
1
vote
1answer
47 views

Link between all NP-complete problems

I have heard a quiet large number of times that "If a polynomial time algorithm for solving an NP-complete problem is made, that means all NP-complete problems are solvable in polynomial time&...
0
votes
0answers
9 views

Complexity of SVP solvers

The complexity of SVP (Shortest Vector Problem) solvers for lattices is always indicated only as a function of the lattice dimension $n$, for example one of the fastest sieve algorithms is the Nearest ...
0
votes
1answer
21 views

Find exactly k columns in binary matrix such that the sum of those columns is the 1-vector

Suppose I have an $M\times N$ binary matrix where $N$ can be large (say $N\approx10^6$). I want to find exactly $k$ columns ($k$ is relatively small, say $k<10$) such that the sum of those $k$ ...
7
votes
0answers
63 views

Can you win the urn depletion game?

In the urn depletion game, you are given several transparent urns containing various colored balls. (For the purposes of this problem, let us assume there are $k=2$ different available ball colors, ...
1
vote
2answers
33 views

Solving QUBO: does the knowledge of the optimal solution help with finding an optimal argument?

Let say I have to solve a large QUBO (quadratic unconstrained binary optimization) problem $$ \min_{x}{x^\top Qx}, $$ where $x\in\{0,1\}^N$ is a binary variable and $Q\in R^{N\times N}$ encodes the ...
0
votes
1answer
22 views

Is Shortest-Spanning-$(u,v)$-Walk NP-complete?

Given an unweighted graph $G$. Here are some definitions that I invented: A walk $W$ is called a spanning walk if $v \in V(G) \implies v\in V(W)$ A $(u,v)$-walk $W$ is a walk of the form $u=v_0, ...
1
vote
0answers
40 views

Are P, NP, PSPACE, and NPSPACE complexity classes?

In Ullman's Introduction to Automata Theory, Languages and Computation, the union theorem (Theorem 12.15) says Let ${f_i(n) | i = 1, 2, ...}$ be a recursively enumerable collection of recursive ...
0
votes
0answers
26 views

Measure of the relative complexity of equations

Is there some measure to compare, in a straightforward way, the complexity of equations? Complexity seen as a function of basic operations involved for solving the equation, or as any other intuitive ...
13
votes
3answers
2k views

How do we know that the P versus NP problem is an NP problem itself?

I have been doing some research on the P versus NP problem. On multiple occasions, I have seen people say that the problem itself is an NP problem. I have been curious about how we know this. If we ...
1
vote
0answers
15 views

Find the maximal Radius of a graph for any removal of a set of up to k vertices

Define $Radius(G=(V,E),k)$ as the maximal radius of a graph constructed from $G$ by removing all vertices in any set $X$ of size up to $k$. More formally: $Radius(G,k) = \underset{X\subseteq{V},|X|\...
0
votes
0answers
17 views

Relating the determinant of a rational matrix to the sizes of its entries' nominators.

Let $D = \left( \frac{p_{ij}}{q_{ij}} \right) \in \mathbb{Q}^{n \times n}, q_{ij} > 0, p_{ij},q_{ij} \text{ coprime, and } \langle p_{ij} \rangle$ the encoding length of the integer $\langle p_{ij} ...
1
vote
0answers
33 views

For $x \in \mathbb{Q}^n$ and $\langle x \rangle$ its encoding length, show: $||x||_1 \leq 2^{\langle x \rangle -n} - 1$.

I'm trying induction on the dimension $n$, based on the (given) inequality $|y| \leq 2^{\langle y \rangle -1} - 1$ for $y \in \mathbb{Q}$. Let $\mathbb{Q}^n \ni x = (x_1,...,x_{n-1},x_n)$, and $\...
6
votes
1answer
126 views

Find the affine transformation to minimize the distance between two sets of points

Definition: Let $A=\{a_1,\cdots,a_n\}$ and $B=\{b_1,\cdots,b_n\}$ two sets with the same cardinality. Then define the distance between two sets as $$d(A,B):=\min_{\sigma}\sum_i||a_i-b_{\sigma(i)}||,\...
0
votes
0answers
12 views

Solving $aX^3 + bY^3 + cZ^3 - dXYZ = 0$ over $\mathbb{F}_q$

I am looking for a way to solve the equation mentioned in the title with $Z\neq 0$ over the finite field $\mathbb{F}_q$ without going through all $q^3$ possibilities. I was thinking: maybe we can ...
0
votes
0answers
19 views

time complexity comparison between $f_1 = \lceil {lg lgn} \rceil! $ , $f_2 = \lceil {lgn} \rceil! $ , $f_3 = n^a $ , $f_4 = b^n $

I am trying to figure out the correct order of the following functions, in terms of the growth rate: $f_1 = \lceil {\lg \lg n} \rceil! $ , $f_2 = \lceil {\lg n} \rceil! $ , $f_3 = n^a $ , $f_4 = b^n $ ...
0
votes
0answers
18 views

Behavior of a simple tag system?

My understanding is that tag systems of TS(2,2) (two symbols, deletion number 2) are supposed to be fairly well understood; they should all be decidable, etc. As near as I can tell, this is the ...
1
vote
1answer
44 views

Feedback Vertex Set NP-complete proof

I have a problem with the final part of the proof. I reduced Vertex Cover to FVS . An instance of the vertex cover problem consists of an undirected graph G = (V,E), and a number k. The decision ...
0
votes
1answer
33 views

What is the complexity of the cramer method?

I was reading this question which says that to solve the cramer method $(n + 1)$ operations are used.Then I thought that the complexity of using the equal method would be given by $ (n + 1) $, but ...
1
vote
0answers
50 views

An Algorithm For Finding Modular Square Roots

I've been working on this algorithm for awhile, and have made some progress, but have hit a stumbling block. For the cases I'm working on, square roots are guaranteed to exist (atleast trivial ones), ...
-3
votes
1answer
39 views

How to solve a fraction of imaginary numbers? [closed]

I have the following equation. $a = \frac{(1/2) - (3/2)i}{(3/2) + (3/2)i}$ The solution says that $a^2 = 5/9$. I don't know how I can perform the steps, could I get some feedback? Thanks!
0
votes
0answers
16 views

Proving $(n-a)! = \omega(2^n)$ for arbitrary $a$

We all know that $n!$ is not exponentially bounded, i.e. $n! = \omega(2^n)$. However, I'm interested in the more general case $(n - a)!$. To prove that this case is also not exponentially bounded, we ...
0
votes
2answers
23 views

If $f(n)$ $\in$ $O(g(n))$ and $O(h(n))$ $\subset$ $O(g(n))$, Can we say that in general $f(n)$ $\not\in$ $O(h(n))$

I have this problem because I want to prove this. For some $k\in \mathbb{Z}^+$, let $f(n) = \sum_{i=1}^{n} i^k$ and let $g(n) = n^k$, approve or disapprove that $f(n) \in O(g(n))$. I did this. (I do ...
0
votes
0answers
28 views

Is the following a good/accurate definition for an enumerator (a kind of Turing machine)?

I am working a bit with a book from Sipser (Introduction to the theory of computation, 3rd Ed.). On page 187 in exercise 3.4 one is asked to give a "..formal definition of an enumerator.[..]" Is the ...
0
votes
0answers
11 views

Formal grammar for the NP-languages?

Suppose $A$ is a finite alphabet, and $L \subset A^*$ is a formal language over it. We call $L$ a P-language iff it is recognised by a deterministic Turing machine in polynomial time and NP-language ...
2
votes
0answers
27 views

Linear programming with approximate arithmetic

One of the big achievements since the 80s is the solution of linear programs, e.g., by barrier method. For example, to solve $$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & ...
1
vote
1answer
31 views

Can this sum of fractions of pairwise sums be computed efficiently?

Given a constant $c \in \mathbb{R}$ and two lists $X, Y \in \mathbb{R}^n$, I want to compute $$ r = \sum_{x \in X} \sum_{y \in Y} \frac{c}{x+y+c} $$ Of course, this can trivially be done with $\...
-1
votes
2answers
36 views

Is this formula related do bynomial coeffient true? [closed]

i have found this relation in my complexity theory exercise, i would like to know where does this formula come from: $${{n}\choose{k}}\approx{n^k} $$ Thank you :)
0
votes
0answers
17 views

Heuristic for Turing Completeness?

I seem to recall that determining whether a language is Turing complete is an undecidable problem in general, but I was wondering what would work as a rule-of-thumb heuristic that strongly suggests it....
0
votes
0answers
14 views

Number Field Sieve complexity in Big-O-Notation

In the paper Pollard J.M. (1993) Factoring with cubic integers. In: Lenstra A.K., Lenstra H.W. (eds) The development of the number field sieve. Lecture Notes in Mathematics, vol 1554. Springer, Berlin,...
10
votes
2answers
149 views

Does the Riemann hypothesis guarantee that integer factorization is difficult?

In an exchange of comments at Is there any mathematical conjecture that is successfully applied in the real world in spite of being yet unproven?, user R.J. Etienne claims that RH guarantees that ...
2
votes
0answers
32 views

Which can be calculated faster? (Fast Fourier Transform)

I am introducing myself in what is Fourier analysis, solving some exercises I ran into a problem that made me curious. Since I don't know much about mathematical formalism, I approached the problem ...
4
votes
1answer
121 views

Most effective algorithms for each step of the basic RSA-Algorithm

I can't seem to find a detailed complexity/runtime analysis of the basic RSA-algorithm from Volker Heun's Book "Fundamentale Algorithmen" on page 275 or any other books which describe it similarly: ...
0
votes
1answer
25 views

Rice theorem and trivial properties for decidability proof

I'm going to have a complexity theory exam and i understood the importance of Rice theorem in proving if given a language $L_{p}=(L|L\space satisfies\space the \space property\space\space p)$, is ...
-1
votes
1answer
23 views

Growth rate of integration

Let $f,g:[0,\infty)\to [0,\infty)$ where $\int_{0}^\infty g(x)dx<\infty$. Is it possible to find $f,g$ such that $$\frac{\int_0^a f(x)g(x)dx}{f(a)\int_a^\infty g(x)dx}$$ grows exponentially on $a$? ...
0
votes
1answer
50 views

Question about SAT and assignment

We know that SAT is an NP problem, so having the answer "yes, it's satisfiable" or "no, it's not satisfiable" requires the work of a non-deterministic Turing Machine with Polynomial execution time. ...
1
vote
1answer
34 views

Good reference that discusses NP hardness in the context of optimization?

Sometimes I read a book on optimization and the author states (without proof) that finding a certain solution to the (non-convex) optimization problem is NP hard. I've learned about complexity theory ...

1
2 3 4 5
54