Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

16
votes
2answers
803 views

Relationship between symmetry and computational intractability?

The $k$-fixed point free automorphism problem asks for a graph automorphism which moves at least $k(n)$ nodes. The problem is $NP$-complete if $k(n)=n^c$ for any $c$>0. However, If $k(n)=O(\log n)$ ...
38
votes
5answers
1k views

Is there a logic without induction that captures much of P?

The Immerman-Vardi theorem states that PTIME (or P) is precisely the class of languages that can be described by a sentence of First-Order Logic together with a fixed-point operator, over the class of ...
20
votes
2answers
887 views

$\ell_p$-norm preserving Turing machines

Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine. For people working ...
16
votes
3answers
736 views

Which $AC^0$ problems are not “truly feasible”?

Neil Immerman's famous Picture of The World is the following (click to enlarge):                    &...
22
votes
1answer
393 views

Are there natural separations in the nondeterministic time hierarchy?

The original Nondeterministic Time Hierarchy Theorem is due to Cook (the link is to S. Cook, A hierarchy for nondeterministic time complexity, JCSS 7 343–353, 1973). The theorem states that for any ...
13
votes
1answer
689 views

Space-time tradeoff lower bounds

Following the discussion on lower bounds for 3SAT [1], I'm wondering what are the main lower bound results formulated as space-time tradeoffs. I'm excluding results such as, say, Savitch's theorem; a ...
2
votes
0answers
266 views

Some problems involving polynomials of public and private variables over GF(2).

Suppose there are a set of low degree (less than some degree $z$) polynomials $P_0, P_1, ..., P_k$ each of which is defined over two types of variables, red variables ${v_r}_0, {v_r}_1, ..., {v_r}_n$ ...
14
votes
1answer
2k views

What are the classic papers from the recursion theoretic area of complexity theory?

Two papers I would include are: D. Kozen, "Indexing of subrecursive classes", STOC, 1978. R. Ladner, "On the Structure of Polynomial Time Reducibility", JACM, 1975.
45
votes
4answers
3k views

Generalized Ladner's Theorem

Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes strictly containing P and strictly contained in NP. The proof uses the completeness of SAT under many-...
38
votes
3answers
8k views

Is optimally solving the n×n×n Rubik's Cube NP-hard?

Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube. Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time ...
1
vote
3answers
851 views

Complexity of a variant of the Mandelbrot set decision problem?

Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number Let Set $M=${$(c,k,m) |$ the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ is unbounded ...
19
votes
1answer
778 views

Do all complexity classes have a leaf language characterization?

Leaf languages are a beautiful way to uniformly define many complexity classes. Most complexity classes are usually specified by a model of computation (e.g., deterministic/randomized TM), and a ...
21
votes
1answer
2k views

Computational complexity of the 3-partition problem with distinct numbers

This question is related to an answer I posted in response to another question. The 3-partition problem is the following problem: Instance: Positive integers a1, …, an, where n=3m and the sum of the ...
5
votes
1answer
275 views

Are there known “completion” operations over languages ?

Assume that $P \neq NP$ and let $NPI = NP \setminus (P \cup NPC)$. Let $L \in NPI$ be a language over an alphabet $\mathcal{A}$. Does there always exist $S \subset \mathcal{A}^*$ such as $(L \cup S) ...
17
votes
2answers
597 views

MIP with efficient provers

It is well-known that the set of languages having two-prover interactive proof systems, in which the verifier runs in polynomial-time (MIP), is NEXP. But are there bounds known on the power of such ...
1
vote
2answers
420 views

Shouldn't relativisation contain consistency proof ?

My question may be stupid, but let's take the Baker-Gill-Soloway theorem as an example : There exists an oracle A such as $P^A = NP^A$ and an oracle B such as $P^B \neq NP^B$. If we take both ...
10
votes
6answers
2k views

Do many-one reductions and Turing reductions define the same class NPC

I wonder if NPC classes defined by many-one reductions and Turing reductions are equal. Edit: Another question, are Turing reductions only collapsing C and co-C classes for some C or is there a class ...
14
votes
3answers
1k views

Is there a complexity theory analogue of Rice's theorem in computability theory?

Rice's theorem states that every nontrivial property of the set recognized by some Turing machine is undecidable. I am looking for complexity-theoretic Rice-type theorem that tells us which ...
1
vote
3answers
578 views

Major conjectures used to prove complexity lower bounds?

Complexity theory uses a large number of unproven conjectures. There are several hardness conjectures in David Johnson's NP-Completeness Column 25. What are the other major conjectures not mentioned ...
3
votes
2answers
320 views

What is the complexity of computing a compatible 3-coloring of a complete graph?

Given a complete graph whose edges are colored by 3 colors, a compatible 3-coloring is a coloring of nodes such that no edge of the graph has the same color as its end-points. The best algorithm I ...
3
votes
1answer
203 views

Sparsity of Horn satisfiability?

Is the set of satisfiable Horn formulas sparse? A sparse language contains a polynomially bounded number of srings at every length.
2
votes
1answer
337 views

What is the most efficient algorithm to sample graphs with trivial automorphism groups ?

Let us call a graph "asymmetric" if it has no nontrivial automorphism group. http://en.wikipedia.org/wiki/Asymmetric_graph I'm looking for an efficient way to compute a random asymmetric graph on a ...
4
votes
1answer
892 views

Is there any natural Karp reduction from Independent Set problem to SAT?

Is there a natural Karp reduction from Independent Set to SAT ? That is, a reduction that does not rely on the Turing machine (as the case in proof of Cook's theorem) but the combinatorial structure.
4
votes
2answers
314 views

What are the different notions of one-way functions?

For instance, A function that is computable but not invertable in log space, Is it one-way function? What are the known definitions of one-way functions? (especially the ones that do not invoke ...
13
votes
1answer
604 views

Circuits with oracles vs. Turing Machines with oracles

Put simply: what is the correspondance between Turing machines with oracles, and uniform circuit families with oracles? How are the latter defined in order to obtain the same computational model, for ...
11
votes
1answer
543 views

what are known bounds on complexity of nontrivial graph automorphism

Given any simple undirected graph G, it is nontrivial to determine if G has nontrivial (non-identity) automorphisms. But what are results on upper/lower bounds of this decision problem?
5
votes
1answer
402 views

High probable polynomial time algorithm for NP-hard problems?

Many NP-complete or NP-hard problems are addressed under the assumption that the problem instances are uniformly distributed. However, it is not true for real world applications. One example is the ...
36
votes
3answers
3k views

Does $VP \neq VNP$ imply $P \neq NP$?

As far as I understand, the geometric complexity theory program attempts to separate $VP \neq VNP$ by proving that the permament of a complex-valued matrix is much harder to compute than the ...
22
votes
2answers
907 views

Is “Experimental Complexity Theory” being used to solve open problems?

Scott Aaronson proposed an interesting challange: can we use supercomputers today to help solve CS problems in the same way that physicists use large particle colliders? More concretely, my ...
1
vote
3answers
1k views

PCP characterization of NP

The PCP theorem (NP= PCP(log n, O(1)) )is a major result in complexity theory with many applications such as proving hardness of approximate results. However, it seems to me that it does not offer any ...
4
votes
4answers
434 views

Are there alternatives to using polynomials in defining the different notions of efficient computation?

Is invoking polynomials in defining the different notions of efficient computation the real obstacle to resolve the P vs NP problem? Do we need a paradigm shift by redefining what constitute an ...
7
votes
4answers
392 views

Complexity class separation in the presence of relativization barriers

Give an example of complexity classes $M$ and $N$ and oracles $A$ and $B$ such that 1. $M^A=N^A$ and 2. $M^B\neq N^B$ and 3. $M \neq N$.
24
votes
6answers
2k views

Are there NP-complete problems with polynomial expected time solutions?

Are there any NP-complete problems for which an algorithm is known that the expected running time is polynomial (for some sensible distribution over the instances)? If not, are there problems for ...
4
votes
1answer
217 views

Unique games conjecture - edge permutations

What do the edge permuations in the unique games conjecture represent?
10
votes
0answers
335 views

Collapsing of exptime and alternation bounded turing machine

This question was already asked on math overflow, but I did not find any answer to my question (or let say the answer was that up to the knowledge of those people, no answer were known) Let C be a ...
10
votes
1answer
334 views

Has the derandomization of slightly non-uniform classes, e.g BPP/linear, been studied?

By BPP/linear I refer to BPP machines with linear advice, which fulfills the promise when given the "correct" advice, and the derandomization should give us, say, a P/linear or (SUBEXP/linear) ...
29
votes
0answers
892 views

Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?

By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e. sub-exponential deterministic simulation which appears correct i.o to every efficient adversary. I think this is a proof: if $EXP\...
3
votes
4answers
2k views

Why is P vs. NP so hard? [closed]

Why is $\mathsf{P}$ vs. $\mathsf{NP}$ problem considered so important? Is $\mathsf{P}$ vs. $\mathsf{NP}$ the hardest mathematical problem? Why is it so hard? All I'm looking for is the hindrances ...
10
votes
6answers
490 views

Reducing complexity with parallelism

Is it possible (slash can you provide an example) to reduce computational complexity of a problem by using a parallel algorithm which does not require a number of processors relative to the input size?...
13
votes
2answers
904 views

Space alternating hierarchy

It is known thanks to Immerman and Szelepcsényi that ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ if $f=\Omega(\log)$ (even for non-space constructible functions). In the same paper, Immerman state that the ...
44
votes
8answers
5k views

The importance of Integrality Gap

I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real ...
0
votes
0answers
441 views

Complexity Theory conferences? [closed]

What are the most significant annual Complexity Theory conferences? Rules: One conference per answer Include a link to the conference
10
votes
3answers
518 views

What evidence is there that $coRP \neq NP$?

What evidence is there that $coRP \neq NP$? $coRP$ is the class of languages for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input ...
12
votes
3answers
520 views

$NP\cap coAM$ Languages

What other problems languages different than graph isomorphism are in $NP\cap coAM$? Can you give some references? Update: I forgot to mention that I'm interested in languages not known to be in $...
18
votes
4answers
1k views

“All-different hypergraph coloring” - known problem?

I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently ...
17
votes
4answers
362 views

Alternate notion of complexity based on gap between brute-force and the best algorithm?

Typically, efficient algorithms have a polynomial runtime and an exponentially-large solution space. This means that the problem must be easy in two senses: first, the problem can be solved in a ...
26
votes
3answers
918 views

Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?

Are there any natural problems in $NP \cap coNP$ that are not (known to be/thought to be) in $UP \cap coUP$? Obviously the big one everyone knows about in $NP \cap coNP$ is the decision version of ...
11
votes
3answers
546 views

Two Variants of NP

Here are two variations on the definition of NP. They (almost certainly) define distinct complexity classes, but my question is: are there natural examples of problems that fit into these classes? (...
31
votes
5answers
2k views

Evidence that PPAD is hard?

There is often-quoted philosophical justification for believing that P != NP even without proof. Other complexity classes have evidence that they are distinct, because if not, there would be "...
44
votes
10answers
3k views

Kolmogorov complexity applications in computational complexity

Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$)...