2022 Developer Survey is open! Take survey.
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
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
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 ...
user avatar
  • 10.3k
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 ...
user avatar
26 votes

Hamiltonian cycle on graphs without small cycles

This unpublished manuscript by Hougardy, Emden-Weinert and Kreuter in 1997 provided a simple proof for the following result which is much stronger than the result pointed out in Kristoffer Arnsfelt ...
user avatar
  • 4,828
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
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,605
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

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 $\...
user avatar
18 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 ...
user avatar
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 ...
user avatar
  • 10.3k
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 ...
user avatar
  • 3,186
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
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 ...
user avatar
  • 3,420
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 ...
user avatar
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.
user avatar
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 ...
user avatar
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 ...
user avatar
  • 16.2k
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
13 votes
Accepted

Hamiltonian cycle on graphs without small cycles

The result is stated in the paper Two New Classes of Hamiltonian Graphs by Arkin, Mitchell and Polinshchuk.
user avatar
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.
user avatar
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 ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
  • 10.3k
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 ...
user avatar
  • 13.5k

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