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,027
30 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 ...
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 ...
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 ...
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 ...
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 ...
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$. ...
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,289
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, ...
22 votes
Accepted

Can typed lambda calculi express *all* algorithms below a given complexity?

I will give a partial answer, I hope others will fill in the blanks. In typed $\lambda$-calculi, one may give a type to usual representations of data ($\mathsf{Nat}$ for Church (unary) integers, $\...
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 ...
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,635
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
19 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: $...
18 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, ...
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

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-...
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 ...
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 ...
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 ...
14 votes
Accepted

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

A proof system for propositional logic is called polynomially bounded, if every tautology $\varphi$ has a proof in the system of length polynomial in the length of $\varphi$. The statement "There ...
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 ...
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 ...

Only top scored, non community-wiki answers of a minimum length are eligible