100 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 ...
user avatar
  • 1,016
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 ...
user avatar
  • 711
45 votes

P and NP classes explanation through lambda-calculus

Turing-machines and $\lambda$-calculus are equivalent only w.r.t. the functions $\mathbb{N} \rightarrow \mathbb{N}$ they can define. From the point of view of computational complexity they seem to ...
user avatar
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 "...
user avatar
  • 1,027
34 votes
Accepted

Is P equal to the intersection of all superpolynomial time classes?

Yes. In fact, by the McCreight-Meyer Union Theorem (Theorem 5.5 of McCreight and Meyer, 1969, free version here) a result of that I believe is due to Manuel Blum, there is a single function $f$ such ...
user avatar
33 votes

The unreasonable power of non-uniformity

A flip answer is that this isn't the first thing about complexity theory that I'd try to explain to a layperson! To even appreciate the idea of nonuniformity, and how it differs from nondeterminism, ...
user avatar
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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
  • 2,271
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 ...
user avatar
28 votes

The unreasonable power of non-uniformity

Here is a "smoothness" argument that I heard recently in defense of the claim that non-uniform models of computation should be more powerful than we suspect. On one hand, we know from the time ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$. ...
user avatar
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 ...
user avatar
  • 2,267
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 ...
user avatar
  • 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" ...
user avatar
  • 5,712
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, ...
user avatar
22 votes
Accepted

Factoring as a decision problem

Here the goal is to construct a decision problem D so that (a) if you can factor you can solve the decision problem in polynomial time and (b) if you can solve the decision problem you can factor in ...
user avatar
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 ...
user avatar
22 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 ...
user avatar
21 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, $\...
user avatar
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)$-...
user avatar
  • 6,615
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-...
user avatar
  • 1,377
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: $...
user avatar
18 votes

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

Shortest 2-Vertex disjoint path problem in undirected graphs recently solved (ICALP14) by A. Bjorklund and T. Husfeldt. But the deterministic solution is for the case of existence of a unique ...
user avatar
  • 3,420
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, ...
user avatar
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 ...
user avatar
  • 1,377
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-...
user avatar

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