Skip to main content
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
32 votes

Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time

There's an algorithm for multiplying an $N \times N^{0.172}$ matrix with an $N^{0.172} \times N$ matrix in $N^2 \operatorname{polylog}\left(N\right)$ arithmetic operations. The main identity used for ...
Josh Alman's user avatar
30 votes
Accepted

Is Descriptive Complexity dead?

I also have the impression that Descriptive Complexity is a less active area of research nowadays. Nevertheless, there are some topics in which people are still active: Rank logics: Rank Logic is ...
Bartosz Bednarczyk's user avatar
29 votes

Most important new papers in computational complexity

The recent paper of László Babai showing that Graph Isomorphism is in Quasi-P is already a classic. Here is a more accessible exposition of the result published in the ICM 2018 proceedings.
27 votes

Theoretical explanations for practical success of SAT solvers?

I am assuming that you are referring to CDCL SAT solvers on benchmark data sets like those used in the SAT Competition. These programs are based on many heuristics and lots of optimization. There were ...
Kaveh's user avatar
  • 21.7k
27 votes
Accepted

What's the status of Babai's Graph isomorphism result?

Aggregating comments by Thomas Klimpel, Sasho Nikolov and Mohammad Al-Turkistany into a community answer: The correction (and hence the quasi-polynomial result) was immediately supported by Harald ...
27 votes
Accepted

Deciding whether an interval contains a prime number

Disclaimer: I'm not an expert in number theory. Short answer: If you're willing to assume "reasonable number-theoretic conjectures", then we can tell whether there is a prime in the interval $[n, n+\...
Noah Stephens-Davidowitz's 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 ...
Pasin Manurangsi's user avatar
26 votes

Most important new papers in computational complexity

In a recent preprint, Harvey and Van Der Hoeven show how to compute Integer multiplication in time $O(n \log n)$ on a multi-tape Turing machine, culminating some 60 years of research (Karatsuba, Toom–...
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
25 votes
Accepted

"Almost all objects have property P" vs. "It is easy to test whether an object has property P"

They are separate (assuming $P \ne NP$). Consider the following property $P(x)$: $x$ is a $2n$-bit string, where either the first $n$ bits are not all zeros, or the last $n$ bits are a yes-instance ...
D.W.'s user avatar
  • 12.2k
25 votes

Theoretical Computer Science vs other Sciences?

As a theoretical computer scientist I am proud of the following achievements of the field. Logicians figured out that all logical connectives can be build from a single one, paving the road for ...
Andrej Bauer's user avatar
  • 29.2k
24 votes
Accepted

Is there an NP-complete language that contains precisely half of the n-bit instances?

I asked this question a few years ago and Boaz Barak positively answered it. The statement is equivalent to the existence of an NP-complete language $L$ where $|L_n|$ is polynomial-time computable. ...
Ryan O'Donnell's user avatar
24 votes

Theoretical explanations for practical success of SAT solvers?

I am typing this quite quickly due to severe time constraints (and didn't even get to responding earlier for the same reason), but I thought I would try to at least chip in with my two cents. I ...
Jakob Nordstrom'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

Is BPP vs. P a real problem after we know BPP lies in P/poly?

Not sure how much of an answer this is, I'm just indulging in some rumination. Question 1 could be equally asked about P $\neq$ NP and with a similar answer -- the techniques/ideas used to prove the ...
usul's user avatar
  • 7,615
22 votes

Most important new papers in computational complexity

Importance is in the eyes of the beholder. However, I would say that the Feder–Vardi CSP dichotomy conjecture, proved independently by A. Bulatov and D. Zhuk, is a seminal result.
22 votes
Accepted

Implications of proving NP=RP on complexity theory

Prelude: the below is just one consequence of $\mathsf{RP}=\mathsf{NP}$ and probably not the most important, e.g. compared to collapse of the polynomial hierarchy. There was a great and more ...
usul's user avatar
  • 7,615
22 votes

Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

Computing a generating set of invariants (sometimes called the computational problem of "Noether's Normalization Lemma") for the action of $SL_3$ on an $n$-dimensional vector space $V$. (You ...
Joshua Grochow's user avatar
22 votes
Accepted

Is the 3-coloring problem NP-hard on graphs of maximal degree 3?

The answer is no: the 3-coloring problem can be solved in linear time on graphs of maximal degree 3 or less, by application of Brooks' theorem. I wasted some time figuring this out, so I thought I'd ...
a3nm's user avatar
  • 9,547
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
21 votes
Accepted

Entropy and computational complexity

Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there ...
Joshua Grochow's user avatar
21 votes

Attempted proofs of P vs NP

Gerhard Woeginger has an up-to-date page with all attempts to (dis)prove the P vs NP question: https://www.win.tue.nl/~gwoegi/P-versus-NP.htm
PsySp's user avatar
  • 840
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
20 votes

Most important new papers in computational complexity

Non-Uniform ACC Circuit Lower Bounds by Ryan Williams: https://people.csail.mit.edu/rrw/acc-lbs.pdf and Classical Verification of Quantum Computations by Urmila Mahadev: http://ieee-focs.org/FOCS-...
19 votes
Accepted

For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?

This question is addressed in Section 2 of [1], which shows (Theorem 2.6) that the problem is in P if $L(\alpha)$ is finite; coNP-complete if $L(\alpha)$ is infinite but bounded (i.e. $L(\alpha)\...
David's user avatar
  • 308

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