Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
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 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

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,765
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
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
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.5k
13 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,615
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
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
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
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,743
11 votes
Accepted

Why is the circuit class AC0 unavoidable?

The class $\mathbf{AC}^0$ arises very naturally as the circuit characterization of problems definable by formulas of first-order logic. A language over the alphabet $\{ 0,1 \}$ is in $\mathbf{AC}^0$ ...
Jan Johannsen's user avatar
11 votes

"Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?

I'm glad you are interested in complexity but there are some issues in your paper. Your techniques relativize and there is an oracle relative to which the Berman-Hartmanis conjecture is true and NP = ...
Lance Fortnow's user avatar
11 votes
Accepted

Does Max Planar 3-SAT admit a PTAS?

Yes, a PTAS for Max-Planar-3-SAT can be constructed by using Brenda Baker's approach. This has been observed, for instance, in Theorem 17 in Pierluigi Crescenzi and LucaTrevisan: "Max NP-...
Gamow's user avatar
  • 5,772
11 votes

PPAD and Quantum

Two answers that I learnt while writing a blog post about this question No: In black-box variants, quantum query/communication complexity offer the Grover quadratic speedup, but not more than that. ...
Aviad Rubinstein's user avatar
11 votes
Accepted

If NP in BPP then NP equals RP

An actual factual reference is K. Ko. Some observations on the probabilistic algorithms and NP-hard problems. Information Processing Letters, 14(1):39–43, 1982. (When I first saw this result --- I ...
Ryan Williams's user avatar
11 votes
Accepted

Complexity class of efficient streaming algorithms

Along with my comment above (noting that not even AC0 is in "StreamL"), let me say that that this class has been studied before; you just need to know what they used to call it. Search for "one-way ...
Ryan Williams's user avatar
11 votes
Accepted

Complete problem in $\Sigma_2^p$ - $\Sigma_{2}SAT$

No. Since universal quantifiers commute with conjunctions, it is easy to see that $\Sigma_2$-SAT with $\psi$ CNF is in NP. If it's really written like this in the book, it's an error. However, the ...
Emil Jeřábek's user avatar
11 votes

Are there any problems whose best known algorithms have running time $n^{\log \log n}$?

The best-known deterministic algorithm for testing polynomial identities given by depth-three diagonal circuits has running time $n^{O(\log \log n)}$ [1]. More explicitly, we are given an expression ...
Robert Andrews's user avatar

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