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 ...
- 20.6k
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 $\...
- 14.9k
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 ...
- 550
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-...
- 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,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 ...
- 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,728
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.9k
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 ...
- 13.4k
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
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