101
votes
Accepted
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
As noted here before, Tardos' example clearly refutes the proof; it gives a monotone function, which agrees with CLIQUE on T0 and T1, but which lies in P. This would not be possible if the proof were ...
- 1,026
94
votes
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
I am familiar with Alexander Razborov whose previous work is extremely crucial and serves as a foundation for Blum's proof. I had the good luck of meeting him today and wasted no time in asking for ...
- 711
40
votes
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
This is posted as community answer because (a) it's not my own words, but a citation from Luca Trevisan on a social media platform or from other people with no CSTheory.SE account; and (b) anyone ...
35
votes
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
The correctness of the claimed proof is being discussed at Luca Trevisan's blog: https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal-np/
In particular "...
- 1,047
30
votes
Problems with big open complexity gaps
The Knot Equivalence Problem.
Given two knots drawn in the plane, are they topologically the same? This problem is known to be decidable, and there do not seem to be any computational complexity ...
- 23.9k
29
votes
Accepted
If P = NP were true, would quantum computers be useful?
The paper "BQP and the Polynomial Hierarchy" by Scott Aaronson directly addresses your question. If P=NP, then PH would collapse. If furthermore BQP were in PH, then no quantum speed-up would be ...
- 5,436
28
votes
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
$
\newcommand{\DSPACE}{\mathsf{DSPACE}}
\newcommand{\L}{\mathsf{L}}
\newcommand{\P}{\mathsf{P}}
\newcommand{\DTIME}{\mathsf{DTIME}}
$
$\L^2 \subseteq \P$ would refute the Exponential Time Hypothesis.
...
- 2,281
28
votes
Accepted
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
The following is an obvious consequence:
$\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ would imply $\mathsf{L} \subsetneq \mathsf{P}$ and therefore $\mathsf{L} \neq \mathsf{P}$.
By the space ...
- 556
26
votes
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
There has, in fact, been quite a lot of recent works on proving quasi-polynomial running time lower bound for computational problems, mostly based on the exponential time hypothesis. Here are some ...
- 306
26
votes
Accepted
Has parameterized complexity led to better algorithms?
There are several examples of problems where a parameterized algorithm performs well in practice. Let me mention two such problems.
In the $k$-Path problem where we are looking for a simple path of ...
- 1,700
24
votes
Problems with big open complexity gaps
Here's a version of the minimum circuit size problem (MCSP): given the $2^n$ bit truth table of a Boolean function, does it have a circuit of size at most $2^{n/2}$?
Known to be not in $AC0$. ...
- 26.7k
24
votes
Problems with big open complexity gaps
The complexity of computing a bit (specified in binary) of an irrational algebraic number (such as $\sqrt{2}$) has the best known upper bound of $\mathsf{P^{{{PP}^{PP}}^{PP}}}$ via a reduction to the ...
- 2,299
24
votes
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
Gustav Nordh commented on by Theorem 5 (page 29). Specifically, the function
$$(x\lor y) \land (\lnot x \lor y) \land (x \lor \lnot y)$$
computes the function which is $1$ only if $x$ and $y$ are ...
- 349
24
votes
Accepted
How "hard" is it to maximize a polynomial function subject to linear constraints?
Your problem is NP-hard, even for polynomials of degree 2.
The crucial reference is
Theodore Motzkin and Ernst Strauss (1965)
"Maxima for graphs and a new proof of a theorem of Turan"
...
- 5,742
23
votes
Accepted
Problems in BQP but conjectured to be outside P
To have a list of such problems, you can look at the list of superpolynomial speed improvement at the quantum algorithm zoo (QAZ). The list below is based on this (see QAZ for precise definitions and ...
23
votes
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
Megiddo and Vishkin proved that Minimum dominating set in tournaments is in $QP$. They showed that tournament dominating set has P-time algorithm iff SAT has subexponential time algorithm. Therefore, ...
- 20.7k
22
votes
Problems with big open complexity gaps
Another natural topological problem, similar in spirit to Peter Shor's answer, is embeddability of 2-dimensional abstract simplicial complexes in $\mathbb{R}^3$. In general it's natural to ask when ...
- 18.1k
20
votes
Accepted
Intersection of languages in NP
Just an extended comment to better explain ARi's comment (I was writing it while I saw it).
It is sufficient to use a "large gap" approach similar to the one used in Lardner's theorem; for example:
$...
- 22.4k
20
votes
Tardos Function Counterexample to Blum's $P\neq NP$ Claim
so these remarks imply that the Tardos function $f$ is the same as
CLIQUE.
Short answer - NO.
It is only a *monotone* "clique-like": accepts all $k$-cliques, and rejects all complete $(k-1)$-...
- 6,655
19
votes
To which complexity class does this language belong?
(as pointed out by Robin the problem is in DP...)
...and it is also DP-complete.
In fact, Jörg Rothe has shown that this even holds for fixed k=4: Jörg Rothe: Exact complexity of Exact-Four-...
- 1,387
17
votes
Problems with big open complexity gaps
Multicounter automata (MCAs) are finite automata equipped with counters that can be incremented and decremented within one step but only take integers >=0 as numbers. Unlike Minsky machines (aka ...
- 1,387
17
votes
Accepted
Potentially equal complexity classes without known contradictory relativizations
I think the biggest such example at present is $BQP $ (quantum polybomial time) vs $PH $ (the polynomial time hierarchy). Significant effort has been put into separating them relative to an oracle, ...
- 26.7k
17
votes
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
Could one use list decoding of Reed-Solomon codes to show Andreev's POLY function is in P, similar to the way Sivakumar did in his membership comparable paper? Or is the POLY function known to be NP-...
- 8,546
16
votes
Accepted
Natural candidates for NP-E and E-NP
TQBF (True Quantified Boolean Formulas) is in E and won't be in NP unless NP = PSPACE.
A language in NP-E is trickier. Such a language would also be in NP-NTIME(n) and we don't have great examples of ...
- 8,546
15
votes
Accepted
What is an equivalent definition of mP/poly in terms of a Turing machine?
There is a notion of a monotone non-deterministic and, more generally, alternating Turing machine in the paper Monotone Complexity by Grigni and Sipser. Since polynomial time is the same as ...
- 4,531
15
votes
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
He has updated his arXiv to say his proof is incorrect:
The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my ...
- 421
14
votes
Accepted
To which complexity class does this language belong?
It is contained in DP: Difference Polynomial-Time, which is also BH$_2$, the second level of the Boolean hierarchy. This class is itself contained in $\Delta^\textrm{P}$, but that is believed to be a ...
- 13.4k
14
votes
Accepted
$\mathsf{EXP}$ vs $\oplus\mathsf{EXP}$
In terms of complexity reasons (rather than complete problems): The Hartmanis-Immerman-Sewelson Theorem should also work in this context, namely: $\mathsf{EXP} \neq \oplus \mathsf{EXP}$ iff there is a ...
- 36.3k
14
votes
What are the relationships between those hypotheses in Fine-Grained Complexity Theory?
This is a recent paper introducing Nondeterministic Strong Exponential Time Hypothesis (NSETH), which is an extension of SETH.
NSETH: For every $\epsilon >0$, there is a $k$ such that $k$-DNF-TAUT ...
- 141
13
votes
Complexity of max problem
It depends how the polytope is represented. In the V-polytope presentation (i.e. $P$ is given in terms of its vertices), the problem is trivial, as Tim mentioned in the comments. In the H-polytope ...
- 18.1k
Only top scored, non community-wiki answers of a minimum length are eligible