103 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 ...
idolvon's user avatar
  • 1,046
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 ...
Mikhail's user avatar
  • 711
41 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 "...
Gustav Nordh's user avatar
  • 1,047
29 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 ...
Sajin Koroth's 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. ...
argentpepper's user avatar
  • 2,281
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 ...
Pasin Manurangsi's 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 ...
Christian Komusiewicz's user avatar
25 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" ...
Gamow's user avatar
  • 5,772
24 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, ...
Mohammad Al-Turkistany's user avatar
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 ...
kdog's user avatar
  • 349
22 votes
Accepted

Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?

It is true that if the function $f$ is given by an oracle, then a randomized algorithm is exponentially faster than any deterministic algorithm. With an oracle function, however, this is not a $BPP$ ...
Andras Farago's user avatar
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: $...
Marzio De Biasi's 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)$-...
Stasys's user avatar
  • 6,685
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, ...
Ryan Williams's user avatar
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-...
Lance Fortnow's user avatar
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 ...
Lance Fortnow's user avatar
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 ...
user541686's user avatar
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 ...
Rosetta's user avatar
  • 141
13 votes

Problems in NC not known to lie in NC2

Disclaimer: I'm not an expert in fast parallel algorithms, hence the probability that I missed more recent results that put the problems I mention in lower levels of the $\mathsf{NC}$ hierarchy is non-...
Geoffroy Couteau's user avatar
13 votes
Accepted

Power of randomness vs. power of indefinite computation

Any problem in ZPP is computable (in fact, it is in the intersection of NP and coNP). Given any ZPP machine, run it in parallel with a deterministic machine that solves the same problem. This affects ...
Yuval Filmus's user avatar
  • 14.3k
13 votes
Accepted

What are the consequences of solving XOR 3-SAT in Logspace?

Take a look at https://www.sciencedirect.com/science/article/pii/S0022000008001141 "The complexity of satisfiability problems: Refining Schaefer's theorem" by Allender et al. which answer your ...
Gustav Nordh's user avatar
  • 1,047
13 votes
Accepted

Structural Complexity Theory References

I don't think there really are canonical references for this stuff (roughly: advanced modern structural complexity theory), but here are some references. This list is partially geared towards my ...
Joshua Grochow's user avatar
12 votes
Accepted

Example of something that’s different for generic and random oracles?

P = UP with a generic (assuming P = PSPACE) but they are separate relative to a random oracle. In the other direction P = Promise-BPP relative to a random but separate relative to a generic. Can't ...
Lance Fortnow's user avatar
12 votes

$BPL$ with polylog random bits is in $L$

It follows from this PRG of Nisan and Zuckerman. This paper shows that if you have an algorithm that uses space $S$ and only $\mathrm{poly}(S)$ random bits, then the number of random bits can be ...
Or Meir's user avatar
  • 5,350
11 votes

Problems with big open complexity gaps

The Skolem problem (given a linear recurrence with integer base cases and integer coefficients, does it ever reach the value 0) is known to be NP-hard and not known to be decidable. As far as I know ...
David Eppstein's user avatar
11 votes

Is there a natural problem in quasi-polynomial time, but not in polynomial time?

Computing VC dimension seems unlikely to be in polynomial time, but has a quasipolynomial time algorithm. Also, it seems hard to detect a planted clique of size $O(\log n)$ in a random graph, but ...
Joe Bebel's user avatar
  • 2,295
11 votes

Uncertainties in GCT program

It depends what you count as "the GCT program." Consider the specific suggestion (GCT I, GCT II) to use the vanishing/nonvanishing of certain multiplicities in the orbit closures of the determinant ...
Joshua Grochow's user avatar
11 votes
Accepted

Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

First, this result is listed in the complexity zoo: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npiconp. Alternatively, it's possible to prove without much trouble (which I do below). We want ...
Mikhail Rudoy's user avatar
11 votes
Accepted

On sparse complete sets and P vs L

Yes, exactly what you suggested is true: if there is a sparse $\mathbf{P}$-complete set under log-space many-one reductions, then $\mathbf{P} = \mathbf{L}$. This was conjectured by Hartmanis in 1978 ...
William Hoza's user avatar
  • 1,733

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