Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

learn more… | top users | synonyms (1)

1
vote
2answers
320 views

Approximating next prime number

Suppose that there is a prime number. Now I want to approximate the next prime number. (It does not have to be exact.) What would be the time-efficient way to do this? Edit: what happens if we limit ...
2
votes
0answers
130 views

reducing #P-complete problem to NP problem

What would be the consequence and meaning of existence of polynomial reduction of #P-complete problem into NP problem (not NP-complete problem)?
0
votes
1answer
70 views

complexity for $f(x)=n!$ and O($2^n$)

Suppose that algorithm has O($n!$). We all know that $n!$ should be smaller than $2^{2^n}$, but bigger than $2^n$. So, will O($n!$) be in EXPTIME (EXP)? Will we able to write O($n!$) as O($2^n$)?
1
vote
1answer
395 views

What is so wrong with polynomial hierarchy collapsing

Many computational complexity researchers believe that finite-level collapse of polynomial hierarchy is unlikely. Why do they believe like this?
4
votes
1answer
90 views

How do we distinguish NP-complete problems from other NP problems?

I just learned that when we have a polynomial algorithm for NP-complete problems, it is possible to use that algorithm to solve all NP problems. So, the question is how we then distinguish ...
2
votes
2answers
153 views

NP-completeness and NP problems

Suppose that someone found a polynomial algorithm for a NP-complete decision problem. Would this mean that we can modify the algorithm a bit and use it for solving the problems that are in NP, but not ...
1
vote
3answers
111 views

Time Complexity of $T(n)=T(n-2)+\frac{1}{\log(n)}$

Solve $T(n)=T(n-2)+\frac{1}{\log(n)}$ for $T(n)$. I am getting the answer as $O(n)$ by treating $1/\log(n)$ as $O(1)$. The recursive call tree of this is a lop-sided tree of height $n$. Hence, ...
1
vote
2answers
1k views

Is there a winning strategy for Scrabble?

I am sure many of us are addicted to the popular Facebook app: Words with Friends, which is basically an online version of Scrabble. In Playing Games with Algorithms:Algorithmic Combinatorial Game ...
10
votes
1answer
283 views

How can I intuit the role of the central limit theorem in breaking the curse of dimensionality for Monte Carlo integration

I would like to more intuitively understand where the power of Monte Carlo integration comes from for large-dimensional domains of integration. Other questions on this site have referenced the proof ...
2
votes
2answers
140 views

Sum set fixpoint, how many iterations?

I want to approach linear equations of the following form over the integers $\mathbb{Z}$: $$x_1 + \cdots + x_n = 0.$$ I stepped over the sum set, which is defined as follows: $$S + T = \{ x + y ...
1
vote
1answer
174 views

Vertex Cover - upper bound

A few definitions: $\mathsf{VC} = \{ (G,k) \mid \text{There exists a vertex cover of size $k$ in $G$}\}$ $\mathsf{VC_{LOG}} = \{ G \mid \text{There exists a vertex cover of size $\leq \log |V|$ in ...
0
votes
1answer
192 views

How do you prove that a game is undecidable?

I'm studying a game that is played on a graph, there are two teams, attackers and defenders. The attackers are attempting to capture the King by occupying all of his neighbours, the defenders are ...
1
vote
1answer
124 views

VP Definition: Why polynomial bound on the degree?

The complexity class $\mathbf{VP}$ (Valiant P) is defined to be the class of all polynomials of polynomially bounded degree which can be realized by an arithmetic circuit family with polynomially ...
6
votes
1answer
533 views

Is there an efficient algorithm to compute a minimal polynomial for the root of a polynomial with algebraic coefficients?

An algebraic number is defined as a root of a polynomial with rational coefficients. It is known that every algebraic number $\alpha$ has a unique minimal polynomial, the monic polynomial with ...
1
vote
1answer
755 views

Worst case of Heapify is $\Omega(n \lg n)$

Worst case of Heapify is $\Omega(n \lg n)$ I know that Heapify is $\Theta(\lg n)$, but I don't know if $\Omega(n \lg n)$ is equivalent. Thanks.
1
vote
1answer
165 views

Sum in tree nodes - algorithm

I've got one very hard problem. Given a tree with nodes with integers. We need to find the largest sum of label values for a set of nodes which does not include any adjacent pair of nodes. ...
9
votes
2answers
847 views

Two $NP$-complete languages whose union is in $P$?

I've been thinking about transformations on $NP$-complete problems that produce languages known to be in $P$. However, I can't seem to find an example of two $NP$-complete languages whose union is in ...
3
votes
1answer
162 views

NP-hardness reduction

Although I know the notion of polynomial time reduction since many years, I am currently confused about the following problem. In a reduction from 3-SAT to 3-Coloring, one constructs (in polytime) a ...
3
votes
1answer
74 views

A card game with a long path

I recently played an online card game in which the cards were spread on the table. The goal was for me to pick up as many as possible, subject to the following rule: After picking up the first card, ...
2
votes
1answer
101 views

A question about sorting

I've always been thought that the fastest way to sort an array of numbers has complexity $O(n \log (n))$. However, radix sort has complexity $O(kn)$ where $k$ is the number of bits. There are even ...
3
votes
1answer
105 views

Determining position at some point in time

I try to solve the following problem. On $n$ parallel railway tracks $n$ trains are going with constant speeds $v_1$, $v_2$, . . . , $v_n$. At time $t$ = 0 the trains are at positions $k_1$, ...
0
votes
1answer
96 views

What is the time complexity of determining coefficients of generating functions?

My question is inspired by the following problem: Given $k$ coins with denominations $\{c_1, ..., c_k\}$, how many ways are there to generate $n$ cents? This can be solved in $\Theta(nk)$ time using ...
1
vote
0answers
53 views

existence of $DLOGTIME$-complete problems

Just curious - is there any problem that can be considered as $DLOGTIME$-complete? Or if not, has it been proven that there does not exist a complete class? (By being complete, I mean that it has ...
1
vote
1answer
32 views

RE problems that are neither RE-complete nor recursive

As stated, is there any decision problems in the complexity class RE that are neither RE-complete nor recursive? It seems that almost all of nonrecursive RE problems are in RE-complete...
0
votes
1answer
58 views

Do the complete areas of various complexity classes have infinitely many problems? [duplicate]

Possible Duplicate: Complexity classes and number of problems I know that almost all of complexity classes that have some significance have infinite number of decision problems. Then what ...
1
vote
2answers
85 views

non-complete problem collapsing to a lower complexity class complete problem

Let us say that there is a NP problem that is not a complete problem. And let us assume that someone found that the problem is in fact P-complete problem. Does this imply P=NP?
0
votes
1answer
22 views

size of first-order formulae to express a property

Let $FO-SIZE[s(n)]$ be the set of properties expressible by uniform sequences of first- order formulas, $\{\phi_{i}\}_{i\in \mathbb{Z^+}}$ , such that the $n$th formula has $O(s(n))$ symbols and ...
2
votes
1answer
423 views

Form or asymptotic behaviour of $T(n) =2T(n-1)+n$ [duplicate]

$T(n) =$ if $n=1$, then time execution is $1$, if $n \geq 2$ then $2T(n-1)+n$ The options are: $T(n) = 2^{n+1} - n - 2$ $T(n) = O(n2^n)$ $T(n) = \Omega(n)$ $T(n) = \theta(2^n)$ Thanks.
2
votes
1answer
85 views

LFP - shortest path problem

Curious question: Can anyone show me how to describe shortest path problem using LFP + first order logic? I am just getting lost on how to describe the problem, though I know that LFP + first-order ...
0
votes
1answer
68 views

Time to resolve a problem of size $1000$ in one second, how time take resolve the same problem of size $10.000$ in $n^2$?

A algorithm require one second to resolve a problem of size $1000$ a local machine. How long time take the same algorithm to resolve the same problem for a problem size of $10.000$ if the algorithm ...
1
vote
1answer
1k views

Big-O notation always holds for this two functions?

For two any functions $f(n)$ and $g(n)$ always holds: $f(n) = O(g(n))$ or $g(n) = O(f(n))$ Right? Thanks
1
vote
1answer
61 views

Descriptive Complexity Theory - operator, structure and iteration?

In descriptive complexity theory, FO is the set of properties (problem) expressible by first-order logic. I get this part, but what are all these transitive operators and some structures? From ...
1
vote
1answer
44 views

Complexity class that is the set of languages expressible by first-order logic

PH is the complexity class that is the set of languages expressible by second-order logic. If so, is there any complexity class that is the set of languages expressible by first-order logic? It seems ...
0
votes
2answers
63 views

Complexity classes and number of problems

Will every complexity class contain infinite number of problems? If they do not, do common complexity classes (e.g. P,NP,PSPACE,EXPTIME,EXPSPACE etc.) contain infinite number of problems?
1
vote
1answer
220 views

example of complexity class that does not have complete problems

Many known complexity classes have complete problems; however, according to what I heard, not all complexity classes have complete problems. So, what are some examples of the complexity classes that ...
3
votes
2answers
5k views

how do you prove that 3-SAT is NP-complete?

As it is, how do you prove that 3-SAT is NP-complete? I know what it means by NP-complete, so I do not need an explanation on that. What I want to know is how do you know that one problem, such as ...
1
vote
0answers
354 views

Polynomial-Time reduction: Clique Problem

Here is an exercise my friend proposed to me: Show that the maximum clique problem polynomial time reduces to the maximum independent set problem. Here is my attempt at solving it: It is known ...
2
votes
1answer
215 views

Using Polynomial-Time Reduction to Prove Hardness

From what I understand of polynomial-time reduction, there are two instances of it: many-one and Turing. Many-one simply breaks down problem A into many instances of problem B, and uses the (known) ...
6
votes
1answer
349 views

What are the prerequisites in order to pursue the P vs. NP problem?

I'm a math major at Berkeley, and am focusing or logics/fundamentals, in particulars groups. I was just trying to see if I were to, for personal interest, get a better understand and perhaps try ...
1
vote
4answers
173 views

A “State Hierarchy” Theorem for Turing Machines?

In complexity theory, there are time hierarchy theorems for Turing machines that show that for certain functions $f$, there exist problems that cannot be solved by a Turing machine in $o(f(n))$ time. ...
1
vote
2answers
94 views

Simplifying a logarithm of a little-o (circuit complexity)

I have an expression which I think is $o(2^n)$, but I'm having difficulty simplifying it: $o(2^n/n)\log(o(2^n/n) + n)$ I can ignore the extra $n$ sitting at the end, since $o(2^n/n) + n = o(2^n/n + ...
0
votes
3answers
215 views

role of constant of proportionality in complexity of algorithm

what is the role of the constant of proportionality while comparing the the order of complexities of two competing algorithms. Like in case ALGO A has complexity 3*O(n) while ALGO B has complexity ...
7
votes
1answer
959 views

Divisor summatory function for squares

The Divisor summatory function is a function that is a sum over the divisor function. $$D(x)=\sum_{n\le x} d(n) = 2 \sum_{k=1}^u \lfloor\frac{x}{k}\rfloor - u^2, \;\;\text{with}\; u = \lfloor ...
3
votes
1answer
530 views

Long integer multiplication using FFT in integer rings

I would like to perform long integer (~= polynomial) multiplication using the FFT or its direct analogue, but never leave integer rings. Please excuse in advance all my mistakes in formulation and ...
1
vote
1answer
81 views

Finding the computational complexity of an algorithm

Algorithm: for (int i = 0; i < 2*n; i += 2) for (int j = n; j >i; j--) foo(); I want to find the number of times foo() is called. ...
-1
votes
1answer
72 views

$T(n) = n^{O(1)}$ iff exists $k > 0$ such that $T(n) = O(n^k)$

I must use O notation to show that: $T(n) = n^{O(1)}$ iff exists $k > 0$ such that $T(n) = O(n^k)$ But, I don't understand what mean: $n^{O(1)}$
2
votes
2answers
2k views

Is $2^{2n} = O(2^n)$?

Is $2^{2n} = O(2^n)$? My solution is: $2^n 2^n \leq C_{1}2^n$ $2^n \leq C_{1}$, TRUE. Is this correct?
2
votes
2answers
1k views

Connecting all points on a plane with shortest path possible

I want to connect N nodes, so all are connected, by connecting each node to their closest neighbors. An image of what I'm looking for is below. Currently I solve it like this: I add a random node to ...
1
vote
1answer
227 views

average distance in a graph

Having a graph of $n$ vertices in Euclidean $m$-dimensional space, is it possible to find average (Euclidean) distance between the vertices in $O(n)$ steps? Is there a deterministic algorithm for ...
2
votes
3answers
2k views

Help proving that $(n+a)^b = \Theta(n^b)$

Please you apologize me by my English. I don't know how make that: $$(n+a)^b = \Theta(n^b), b > 0$$ I know, I must to find two constants such that: $$ c_{1} n^b \leq (n+a)^b \leq c_{2} n^b $$ I ...