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 ...
- 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 ...
- 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.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 ...
- 20.5k
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 ...
- 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 ...
- 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,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-...
- 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 $\...
- 14.7k
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 ...
- 560
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.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 ...
- 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-...
- 8,546
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,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 ...
- 551
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.
- 2,718
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 ...
- 35.6k
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.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 ...
- 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 ...
- 13.3k
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 ...
- 411
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.
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.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 ...
- 13.5k
Only top scored, non community-wiki answers of a minimum length are eligible