Questions tagged [complexity-classes]

Computational complexity classes and their relations

34
votes
2answers
2k views

Semantic vs. Syntactic Complexity Classes

In his "Computational Complexity" book, Papadimitriou writes: RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the ...
30
votes
5answers
5k views

NEXP-complete problems

There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one ...
54
votes
2answers
3k views

Can one amplify P=NP beyond P=PH?

In Descriptive Complexity, Immerman has Corollary 7.23. The following conditions are equivalent: 1. P = NP. 2. Over finite, ordered structures, FO(LFP) = SO. This can be thought of as "...
17
votes
1answer
470 views

Looking for a nice problem inside SC but not in the first two levels

The complexity zoo doesn't have much about the $\mathsf{SC}$. I am looking for a nice$^\dagger$ problem that is in higher levels of the hierarchy, i.e. a problem in $\mathsf{DTimeSpace}(n^{O(1)},\lg^{...
21
votes
2answers
1k views

Problem in BPP but not known to be in RP or co-RP

Is there an example of a natural problem that's in BPP but that's not known to be in RP or co-RP?
19
votes
1answer
1k views

Consequences of UP equals NP

EDIT at 2011/02/08: After some references finding and reading, I decided to separate the original question into two separate ones. Here's the part concerning UP vs NP, for the syntactic and semantic ...
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 ...
16
votes
2answers
1k views

Is NP in $DTIME(n^{poly\log n})$?

Is NP in $DTIME(n^{poly\log n})$?
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 ...
27
votes
2answers
1k views

What are the consequences of Parity-L = P?

Parity-L is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero ...
22
votes
3answers
1k views

Problems outside of P that are not P-hard

While reading an answer by Peter Shor and an earlier question by Adam Crume I realized that I have some misconceptions about what it means to be $\mathsf{P}$-hard. A problem is $\mathsf{P}$-hard if ...
12
votes
2answers
1k views

Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?

By http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf If $A$ is a PSPACE-complete language, $P^{A}=NP^{A}$. If $B$ is a deterministic polynomial-time oracle, $P^{B}\ne NP^{B}$ (assuming $P\...
18
votes
1answer
437 views

Natural candidate against the Isomorphism Conjecture?

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic (p-isomorphic) to each other. The key significance of the conjecture is ...
233
votes
11answers
115k views

Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct? Also on topic: where else (on the internet) is its correctness being discussed? Note: the focus of this question text has ...
26
votes
3answers
1k views

Succinct Problems in $\mathsf{P}$

The study of Succinct representation of graphs was initiated by Galperin and Wigderson in a paper from 1983, where they prove that for many simple problems like finding a triangle in a graph, the ...
24
votes
3answers
2k views

Hardness of approximation - additive error

There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for ...
46
votes
4answers
1k views

What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?

We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq $ $\mathsf{polyL}$, where $\mathsf{L}^2 = \mathsf{...
37
votes
4answers
1k views

Examples where the uniqueness of the solution makes it easier to find

The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. ...
30
votes
4answers
3k views

Consequences of NP=PSPACE

What would be the nasty consequences of NP=PSPACE? I am surprised I did not found anything on this, given that these classes are among the most famous ones. In particular, would it have any ...
25
votes
4answers
2k views

Why do equalities between complexity classes translate upwards and not downwards?

Hey Guys, I understand that the padding trick allows us to translate complexity classes upwards - for example $P=NP \rightarrow EXP=NEXP$. Padding works by "inflating" the input, running the ...
23
votes
3answers
878 views

What are the relationships between those hypotheses in Fine-Grained Complexity Theory?

Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. "Fine-grained" ...
21
votes
3answers
774 views

Limits to Parallel Computing

I am curious in a broad sense about what is known about parallelizing algorithms in P. I found the following wikipedia article about the subject: http://en.wikipedia.org/wiki/NC_%28complexity%29 The ...
11
votes
4answers
733 views

Does diagonalization captures the essence of class separation ?

I don't remember having seen a class separation not based on diagonalization and relativization results. Diagonalization could still be used to separate remaining known classes, because non-...
19
votes
4answers
856 views

Parity and $AC^0$

Parity and $AC^0$ are like inseparable twins. Or so it has seemed for the last 30 years. In the light of Ryan's result, there will be renewed interest in the small classes. Furst Saxe Sipser to Yao ...
19
votes
1answer
750 views

Is there a better than linear lower bound for factoring and discrete log?

Are there any references that provide details about circuit lower bounds for specific hard problems arising in cryptography such as integer factoring, prime/composite discrete logarithm problem and ...
12
votes
1answer
359 views

Time Hierarchies in DSPACE(O(s(n)))

The time hierarchy theorem states that turing machines can solve more problems if they have (enough) more time. Does it hold in some way if the space is limited asymptotically? How does $\textrm{DTISP}...
21
votes
2answers
697 views

What is the big version of NC?

$\mathsf{NC}$ captures the idea of efficiently parallelizable, and one interpretation of it is problems that are solvable in time $O(\log^c n)$ using $O(n^k)$ parallel processors for some constants $c$...
23
votes
4answers
935 views

What are the compelling reasons for believing $L\neq P$?

What are the compelling reasons for believing $L\neq P$? L is the class of log-space algorithms with pointers to the input. Suppose L=P for the moment. What would a log-space algorithm for a P-...
18
votes
1answer
1k views

Cutting-sticks puzzle

Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2. Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time? ...
9
votes
3answers
468 views

Benefits for syntactic and semantic classes

This is a post separated from Consequences of UP equals NP, and also a follow-up question to Semantic vs. Syntactic Complexity Classes. In the above post we learned about the semantic and syntactic ...
8
votes
1answer
1k views

Reducing #SAT to #MONOTONE-2SAT

The problem #MONOTONE-2SAT is known to be #P-complete. This means that #SAT can be reduced to it. My question is: given a #SAT instance $F$, which is the transformation that converts $F$ to its ...
14
votes
2answers
856 views

Quantum analogues of SPACE complexity classes

We often consider complexity classes where we are bounded in the amount of space our Turing machine can use, for example: $\textbf{DSPACE}(f(n))$ or $\textbf{NSPACE}(f(n))$. It seems that early in ...
13
votes
1answer
667 views

Is Quasi-polynomial time in PSPACE?

I had done some search on this but I was not able to find an answer either way. Huck answered it fully. Thanks :)
17
votes
1answer
592 views

What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$?

Following Josh Grochow's suggestion, I am converting my comment from a previous question into a new question. What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$? Here $\mathsf{UP}$ is the ...
6
votes
2answers
584 views

Is there a PSPACE-intermediate language?

Suppose PH is strictly contained in PSPACE. Is there a problem in PSPACE that is not in PH and not PSPACE-complete? I encountered a language that is in PSPACE. The question is whether it's in PH. So ...
16
votes
2answers
1k views

Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$?

In the "last paragraph" of the "first page" of the following paper: Vikraman Arvind, Johannes Köbler, Uwe Schöning, Rainer Schuler, "If NP Has Polynomial-Size Circuits, then MA = AM," Theoretical ...
10
votes
1answer
282 views

A natural problem in $\textrm{S}_2^\textrm{P}$?

The complexity class $\textrm{S}_2^\textrm{P}$ is defined as follows (from Wikipedia): A language $L$ is in $S_2^P$ if there exists a polynomial-time predicate $P$ such that If $x \in L$, ...
59
votes
8answers
3k views

What is the complexity class most closely associated with what the human mind can accomplish quickly?

This question is something I've wondered about for a while. When people describe the P vs. NP problem, they often compare the class NP to creativity. They note that composing a Mozart-quality ...
37
votes
7answers
6k views

What do we know about provably correct programs?

The ever increasing complexity of computer programs and the increasingly crucial position computers have in our society leaves me wondering why we still don't collectively use programming languages in ...
32
votes
3answers
859 views

An Anthology of Complexity Assumptions

In the paper The Random Oracle Hypothesis Is False, the authors (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi) discuss the implications of the random-oracle hypothesis. They argue ...
32
votes
8answers
3k views

Problems with big open complexity gaps

This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves. To be more ...
22
votes
6answers
2k views

Statements that imply $\mathbf{P}\neq \mathbf{NP}$

This is sort of an open-ended question - for which I apologize in advance. Are there examples of statements that (seemingly) don't have anything to do with complexity or Turing machines but the ...
33
votes
3answers
2k views

complexity of greatest common divisor (gcd)

Consider the following counting problem (or the associated decision problem): Given two positive integers encoded in binary, compute their greatest common divisor (gcd). What is the smallest ...
26
votes
2answers
1k views

Ladner's Theorem vs. Schaefer's Theorem

While reading the article "Is it Time to Declare Victory in Counting Complexity?" over at the "Godel's Lost Letter and P=NP" blog, they mentioned the dichotomy for CSP's. After some link following, ...
26
votes
3answers
2k views

Consequences of #P = FP

Which would be the consequences of #P = FP? I'm interested in both practical and theoretical consequences. From a practical point of view, I'm particularly interested in consequences on Artificial ...
20
votes
1answer
681 views

“Almost easy” NP-complete problems

Let us say that a language $L$ is P-density-close if there is a polynomial time algorithm that correctly decides $L$ on almost all inputs. In other words, there is an $A\in$ P, such that $L\Delta 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 ...
21
votes
1answer
1k views

What is the current known hardness of Graph Isomorphism?

Inspired by the question is factoring known to be P-hard, I wonder what the current similar state of knowledge is about the hardness of graph isomorphism. I am sure that it is currently not known if ...
29
votes
3answers
914 views

Is NPI contained in P/poly?

It is conjectured that $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ since the converse would imply $\mathsf{PH} = \Sigma_2$. Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\...
11
votes
3answers
1k views

Does P contain incomprehensible languages? (TCS community wiki)

Answer: not known Many thanks to all who helped refine this question and the definitions associated to it. The definitions of this wiki provided the starting point for the more recent TCS wiki "...