Questions tagged [complexity-classes]
Computational complexity classes and their relations
670
questions
231
votes
11
answers
121k
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 ...
- 1,679
63
votes
8
answers
4k
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 ...
user1338
55
votes
2
answers
4k
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 "...
- 18.9k
49
votes
4
answers
2k
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{...
- 2,281
44
votes
3
answers
7k
views
P and NP classes explanation through lambda-calculus
In the introduction and explanation P and NP complexity classes often given through Turing machine.
One of the model of computation is the lambda-calculus.
I understand, that all of models of ...
- 541
41
votes
2
answers
4k
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 ...
- 16.5k
39
votes
7
answers
7k
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 ...
- 4,670
38
votes
3
answers
4k
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 ...
- 383
38
votes
4
answers
2k
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. ...
- 11.3k
37
votes
8
answers
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 ...
- 8,598
37
votes
5
answers
9k
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 ...
36
votes
2
answers
2k
views
Consequences of $SAT \in BQP$
As a TCS amateur, I'm reading some popular, very introductory material on quantum computing. Here are the few elementary bits of information I've learned so far:
Quantum computers are not known to ...
- 6,780
35
votes
1
answer
2k
views
$BQP$ vs $QMA$?
The central problem of complexity theory is arguably $P$ vs $NP$.
However, since Nature is quantum, it would seem more natural to consider the classes $BQP$ (ie decision problems solvable by a ...
35
votes
3
answers
1k
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 ...
34
votes
5
answers
4k
views
The unreasonable power of non-uniformity
From the common sense point of view, it is easy to believe that adding non-determinism to $\mathsf{P}$ significantly extends its power, i.e., $\mathsf{NP}$ is much larger than $\mathsf{P}$. After all,...
- 11.3k
34
votes
3
answers
3k
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 ...
- 451
34
votes
5
answers
3k
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 "...
- 9,850
31
votes
4
answers
5k
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 ...
- 8,598
30
votes
0
answers
779
views
The complexity of checking whether two DAG have the same number of topological sorts
This problem is highly related to the CNF one.
Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No".
...
- 709
29
votes
2
answers
2k
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 ...
- 8,821
29
votes
4
answers
6k
views
If P = NP were true, would quantum computers be useful?
Suppose that P = NP is true. Would there then be any practical application to building a quantum computer such as solving certain problems faster, or would any such improvement be irrelevant based on ...
user1338
29
votes
3
answers
1k
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 $\...
- 2,151
29
votes
0
answers
1k
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\...
28
votes
2
answers
2k
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, ...
- 2,786
28
votes
3
answers
1k
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 ...
- 36.9k
28
votes
1
answer
1k
views
Is uniform RNC contained in polylog space?
Log-space-uniform NC is contained in deterministic polylog space (sometimes written PolyL). Is log-space-uniform RNC also in this class? The standard randomized version of PolyL should be in PolyL, ...
- 1,801
27
votes
3
answers
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 ...
- 1,344
26
votes
3
answers
1k
views
Optimization problems with minimax characterization, but no polynomial-time algorithm
Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the ...
- 11.3k
26
votes
3
answers
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 ...
- 6,780
26
votes
2
answers
961
views
What are the consequences of $L = \oplus L$?
Shiva Kintali has just announced a (cool!) result that graph isomorphism for bounded treewidth graphs of width $\geq 4$ is $\oplus L$-hard. Informally, my question is, "How hard is that?"
We know ...
- 6,994
25
votes
4
answers
3k
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 ...
- 1,548
25
votes
3
answers
955
views
Constructivity in Natural Proof and Geometric Complexity
Recently, Ryan Willams proved that Constructivity in Natural Proof is unavoidable to derive a separation of complexity classes : $\mathsf{NEXP}$ and $\mathsf{TC}^{0}$.
Constructivity in Natural ...
- 251
25
votes
3
answers
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 ...
- 3,950
25
votes
1
answer
785
views
What is $\mathsf{NP}$ restricted to linear size witnesses?
This is related to the question Is the Witness Size of Membership for Every NP Language Already Known?
Some natural $\mathsf{NP}$(-complete) problems have linear length witnesses: a satisfying ...
- 2,281
25
votes
3
answers
1k
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" ...
user17918
25
votes
1
answer
2k
views
Tardos Function Counterexample to Blum's $P\neq NP$ Claim
In this thread, Norbet Blum's attempted $P \neq NP$ proof is succinctly disproved by noting that the Tardos function is a counterexample to Theorem 6.
Theorem 6: Let $f \in \mathcal{B}_n$ be any ...
- 371
24
votes
7
answers
3k
views
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
László Babai recently proved that
the Graph Isomorphism problem is in quasipolynomial time.
See also his
talk at University of Chicago,
note from the talks by Jeremy Kun
GLL post 1,
GLL post 2,
GLL ...
user17918
24
votes
2
answers
1k
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$...
- 10.2k
24
votes
1
answer
917
views
Is P equal to the intersection of all superpolynomial time classes?
Let us call a function $f(n)$ superpolynomial if $\lim_{n\rightarrow\infty} n^c/f(n)=0$ holds for every $c>0$.
It is clear that for any language $L\in {\mathsf P}$ it holds that $L\in {\mathsf {...
- 11.3k
23
votes
3
answers
1k
views
Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
- 231
23
votes
4
answers
1k
views
Can typed lambda calculi express *all* algorithms below a given complexity?
I know that the complexity of most varieties of typed lambda calculi without the Y combinator primitive is bounded, i.e. only functions of bounded complexity can be expressed, with the bound becoming ...
- 8,911
23
votes
4
answers
1k
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-...
- 239
23
votes
6
answers
3k
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 ...
23
votes
1
answer
972
views
Is there any justification to believe that $NL\neq L$?
I wonder if there is any justification to believe that $NL=L$ or to believe that $NL\neq L$?
It is known that $NL \subset L^2$.
The literature on derandomization of $RL$ is pretty convincing that $RL=...
- 903
23
votes
1
answer
1k
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 ...
- 13.5k
22
votes
4
answers
2k
views
Communication Complexity ...Classes?
Discussion:
I've been spending some personal time lately learning various things in communication complexity. For instance, I've re-familiarized myself with the relevant chapter in Arora/Barak, ...
- 5,961
22
votes
3
answers
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 ...
- 10.2k
22
votes
3
answers
995
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 ...
- 221
22
votes
1
answer
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 ...
- 905
22
votes
0
answers
773
views
What is the power of general poly-size permutation branching programs?
Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of permutation branching programs, which are layered branching programs (i.e., the ones defined here) whose transitions ...
- 5,273