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
31 votes

Are there any hard instances of 3-SAT when the clauses can only use literals that are "nearby" each other?

No. If the 3-SAT instance has $m$ clauses, then you can test satisfiability in $O(m 2^N)$ time. Since $N$ is a fixed constant, this is a polynomial-time algorithm that solves all instances of your ...
  • 10.5k
27 votes
Accepted

Did "Where the really hard problems are" hold up? What are current ideas on the subject?

Here is a rough summary of the status based on a presentation given by Vardi at a Workshop on Finite and Algorithmic Model Theory (2012): It was observed that hard instances lie at the phase ...
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
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,377
19 votes
Accepted

If BQP contains NP, does this mean that P=NP?

No, $\mathrm{NP}\subseteq\mathrm{BQP}$ is not known to imply $\mathrm P=\mathrm{NP}$. Even the stronger assumption $\mathrm{NP}\subseteq\mathrm{BPP}$ is not known to yield a deeper collapse than $\...
18 votes
Accepted

Password hashing using NP complete problems

Unfortunately, this doesn't seem to work (see below for details), and it seems hard to find a way to make this kind of idea yield a provably secure scheme. The problem with your general idea You're ...
  • 10.5k
17 votes
Accepted

Is there a natural problem on the naturals that is NP-complete?

This problem has a variation with a single integer input: Does $n$ have a divisor strictly in between its two largest prime factors? The idea is to use the same randomized reduction from subset ...
17 votes

Are there interesting graph classes where the treewidth is hard (easy) to compute?

Treewidth is NP-hard to compute on co-bipartite graphs, indeed the original NP-hardness proof of treewidth of Arnborg et al. shows this. Additionally, Bodlaender and Thilikos showed that it is NP-hard ...
  • 3,236
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-...
17 votes

Are there any hard instances of 3-SAT when the clauses can only use literals that are "nearby" each other?

Incident graph of a SAT formula is a bipartite graph that has a vertex for each clause and each variable. We add edges between a clause and all of its variables. If the incident graph has bounded ...
  • 3,430
17 votes
Accepted

Relationship between two graph optimization problems

One example: choosing the property "G contains a node that has an edge to all nodes in G" makes P1 trivial in $O(n + m)$ (pick node with largest degree), but makes P2 the problem of finding the ...
16 votes
Accepted

Is optimally solving the n×n×n Rubik's Cube NP-hard?

One of my papers was just posted to arXiv and addresses this question: optimally solving the Rubik's Cube is NP-complete.
16 votes
Accepted

Problems that are counter-intuitively solvable in practice?

Highly structured SAT instances (even on millions of variables) can often be solved in practice. However, random SAT instances near the satisfiability threshold with even a few hundred variables are ...
15 votes
Accepted

Probability of generating a desired permutation by random swaps

I think that whether p>0 can be decided in polynomial time. The problem in question can be easily cast as the edge-disjoint paths problem, where the underlying graph is a planar graph consisting ...
  • 16.3k
15 votes

Did "Where the really hard problems are" hold up? What are current ideas on the subject?

Yes, there has been a lot of work since Cheeseman, Kanefsky and Taylor's 1991 paper. Doing a search for reviews of phase transitions of NP-Complete problems will give you plenty of results. One such ...
  • 2,756
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

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

Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?

You're right that the standard reduction from 3-SAT to 3D-matching (3DM) is not parsimonious. For the record, here's a sketch of a reduction that is parsimonious. It is obtained by composing ...
  • 8,301
13 votes
Accepted

Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

I believe the problem to be coNP-complete. I have uploaded it as an arXiv preprint.
13 votes
Accepted

Is it still open to determine the complexity of computing the treewidth of planar graphs?

As far as I know the NP-completeness of computing the treewidth of a planar graph is still open. The most recent reference I know is a survey by Bodlaender from 2012 called `Fixed-Parameter ...
  • 5,225
13 votes
Accepted

NP-hardness of coloring uniform hypergraphs

$2$-coloring $s$-uniform hypergraphs is also called Set Splitting, problem [SP4] in Garey-Johnson book. The hardness proof is due to Lovasz in this paper.
  • 4,828
13 votes
Accepted

Does P = NP imply NP being a strict subset of PSPACE?

No. It is possible (as far as we know) that $\textbf{P} = \textbf{NP} = \textbf{PSPACE}$. If $\textbf{P} = \textbf{NP}$, the polynomial hierarchy collapses, i.e., $\textbf{P} = \textbf{PH}$. See ...
  • 10.5k
13 votes
Accepted

Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

It is NP-hard for $k=3$. The reduction is from 3-SAT-(2,2), which means that every clause contains $3$ literals and every literal occurs in at most $2$ clauses. First of all, for simplicity, let's ...
  • 13.7k
13 votes

Problems that are counter-intuitively solvable in practice?

The Hindley-Milner type system is used in functional programming languages (Haskell, SML, OCaml). The type-inference algorithm is nearly linear in practice and works amazingly well, but is known to be ...
  • 26.8k

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