97
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 his opinion on this whole matter, on whether he had even seen the proof or not and what are his thoughts about it if he did.
To my surprise, he replied that he ...
96
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 correct, since the proof applies to this case too. However, can we pinpoint the mistake? Here is, from a post on the lipton's blog, what seems to be the place ...
84
Here is a further intuitive and unpretentious explanation along the lines of MGwynne's answer.
With $2$-SAT, you can only express implications of the form $a \Rightarrow b$, where $a$ and $b$ are literals. More precisely, every $2$-clause $l_1 \lor l_2$ can be understood as a pair of implications: $\lnot l_1 \Rightarrow l_2$ and $\lnot l_2 \Rightarrow l_1$. ...
47
Showing that your problem is in coAM (or SZK) is indeed one of the main ways to adduce evidence for "hardness limbo." But besides that, there are several others:
Show that your problem is in NP ∩ coNP. (Example: Factoring.)
Show that your problem is solvable in quasipolynomial time. (Examples: VC dimension, approximating free games.)
Show that your ...
44
László Lovász, Coverings and coloring of hypergraphs, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math., Winnipeg, Man., 1973, pp. 3--12, proved that Chromatic number reduces to 3-colourability.
I think, that is the first proof for NP-completeness of 3-colourability.
Here is Lovász's paper; ...
43
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 should feel free to update this with updated, relevant information.
Quoting Luca Trevisan from a public Facebook post (08/14/2017), replying to a question about ...
37
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 "anon" posted the following relevant comment:
"Tardos observed that Razborov’s and Alon-Boppana’s arguments carry over to a function which is computed by a ...
33
Based on the discussion, I’ll repost this as an answer.
As proved by Manders and Adleman, the following problem is NP-complete: given natural numbers $a,b,c$, determine whether there exists a natural number $x\le c$ such that $x^2\equiv a\pmod b$.
The problem can be equivalently stated as follows: given $b,c\in\mathbb N$, determine whether the quadratic $x^...
31
Consider resolution on a 2-SAT formula. Any resolvent is of size at most 2 (note that $n + m -2 \le 2$ if $n, m \le 2$ for clauses of length $n$ and $m$ resp). The number of clauses of size 2 is quadratic in the number of variables. Therefore, the resolution algorithm is in P.
Once you get to 3-SAT you can get bigger and bigger resolvents, so it all goes ...
30
Although it seems intuitive that the list of forbidden (induced) subgraphs for a class $\mathscr{C}$ of graphs which has NP-hard recognition should possess some "intrinsic" complexity, I have recently found some striking negative evidence to this intuition in the literature.
Perhaps the simplest to describe is the following, taken from an article by B. ...
30
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 problem.
The algorithm works in $m$ stages. Let $\varphi_i$ denote the formula consisting of the clauses that use only variables from $x_1,\dots,x_i$. Let $...
27
It seems the issue is the kind of reductions used for each of them, and they are using different ones: they probably mean "$\mathsf{NP}$-hard w.r.t. Cook reductions" and "$\mathsf{NP}$-complete w.r.t. Karp reductions".
Sometimes people use the Cook reduction version of $\mathsf{NP}$-hardness because it is applicable to more general computational problems (...
26
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 Hansen's answer:
For any given rational number $0\le r <1/2$, the Hamiltonian cycle probem remains NP-complete even if restricted to bipartite planar $n$-...
26
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 both $1$, hence it is monotone. The expression above for the function represents a "standard network" $\beta$ (where the only negations are to a literal) whose ...
25
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 transition from under- to over-constrained region. The fundamental conjecture is that there is strong connection between phase-transitions and computational complexity ...
answered Jan 23 '17 at 14:16
Mohammad Al-Turkistany
13.9k4 gold badges49 silver badges130 bronze badges
23
You need to understand that $\mathsf{CSP}$ problems have a structure that generic $\mathbf{SAT}$ problems do not have. I will give you a simple example. Let $\Gamma=\{\{(0,0),(1,1)\},\{(0,1),(1,0)\}\}$. This language is such that you can only express equality and inequality between two variables. Clearly any such set of constraints is ...
23
The most recent paper on this question seems to be:
Noam Livne, A note on #P-completeness of NP-witnessing relations,
Information Processing Letters, Volume 109, Issue 5, 15 February 2009, Pages 259–261
http://www.sciencedirect.com/science/article/pii/S0020019008003141
which gives some sufficient conditions.
Interestingly the introduction states "To date,...
23
Here are three additions to Scott's list:
Show your problem is in fewP. This means that the number of solutions is bounded by some polynomial. (Example: Turnpike problem). No NP-complete problem is known to be in fewP. (impossible unless fewP=NP).
Show your problem is in $LOGNP$ or in $NP[log^2n]$ (Can be solved using limited number of nondeterministic ...
answered Feb 6 '14 at 8:04
Mohammad Al-Turkistany
13.9k4 gold badges49 silver badges130 bronze badges
22
I recommend Jenga!
Assuming you have two perfectly logical, sober, and dextrous players, Jenga is a perfect-information two-player game, just like Checkers or Go. Suppose the game starts with a stack of $3N$ bricks, with 3 bricks in each level. For most of the game, each player has $\Theta(N)$ choices at each turn for the next move, and in the absence of ...
22
From the comment above: if a problem seems hard enough, but you are not able to prove that it is NP-complete, a quick check is to count the number of strings of length $n$ in the language: if the set is sparse it is unlikely to be NPC, otherwise P=NP by Mahaney's theorem ... so it's better to direct efforts towards proving that it is in P :-) :-)
An example ...
21
A new paper by Demaine, Demaine, Eisenstat, Lubiw, and Winslow makes partial progress on this question---it gives a polynomial-time algorithm for optimally solving $n \times O(1) \times O(1)$ cubes, and shows $\mathsf{NP}$-hardness for optimally solving what you might call "partially-colored" cubes.
It also shows that the $n \times n \times n$ cube's ...
21
Here is a simple reduction for the TSP problem to the metric TSP problem:
For the given TSP instance with $n$ cities, let $D(i,j) \geq 0$ denote the distance between $i$ and $j$. Now let $M = \max_{i,j} D(i,j)$. Define the metric TSP instance by the distances $D'(i,j) := D(i,j)+M$. To see that this gives a metric TSP instance, let $i,j,k$ be arbitrary. Then ...
answered Oct 22 '12 at 15:02
Kristoffer Arnsfelt Hansen
3,8962 gold badges21 silver badges34 bronze badges
21
Here's a reasonably natural one: on an input $(G,k)$, determine whether $G$ has a connected regular subgraph with at least $k$ edges. For 3-regular graphs this is trivial, but if max degree is 3 and the input is connected, not a tree, and not regular, then the largest such subgraph is the longest cycle, so the problem is NP-complete.
21
No.
Turing-recognizable undecidable languages can be unary (define $x \not\in L$ unless $x = 0000\ldots 0$, so the only difficult strings are composed solely of 0's). Mahaney's theorem says that no unary language can be NP-complete unless P=NP.
21
Here is another paper from 1973 that proves that 3-colorability is NP-hard.
Larry J. Stockmeyer. “Planar 3-colorability is polynomial complete.” ACM SIGACT News, vol. 5, no. 3, 1973.
(It seems that Lovász and Stockmeyer obtained their results independently.)
Update: see comments below.
21
If P=NP, there must be polynomial-time algorithms for NP-complete problems. However, there might not be any algorithm that provably solves an NP-complete problem and provably runs in polynomial time.
21
A rainbow matching in an edge-colored graph is a matching whose edges have distinct colors. The problem is: given an edge-colored graph $G$ and an integer $k$, does $G$ have a rainbow matching with at least $k$ edges? This is known as rainbow matching problem, and its NP-complete even for properly edge-colored paths. The authors even note that prior to this ...
20
As Walter says, clauses of 2-SAT have a special form. This can be exploited to find solutions quickly.
There are actually several classes of SAT instances that can be decided in polynomial time, and 2-SAT is just one of these tractable classes. There are three broad kinds of reasons for tractability:
(Structural tractability) Any class of SAT instances ...
20
This problem is the same as the Vertex Cover problem for $3$-uniform hypergraphs:
given a collection $H$ of subsets of $V$ of size $3$ each, find a minimal subset $U\subseteq V$ that intersects each set in $H$.
It is therefore NP-hard, but fixed parameter tractable.
It is also NP-hard to approximate to within a factor of $2-\epsilon$ for every $\epsilon&...
20
No, you can not identify the sum of two permutations in polynomial time unless P=NP. Your problem is NP-complete since the decision version of your problem is equivalent to the NP-complete problem $2$-Numerical Matching with target sums:
Input: Sequence of $a_1, a_2, \ldots a_n$ of positive integers, $\sum_{i=1}^n a_i = n(n+1)$, $1 \le a_i \le 2n$ for $1 \...
answered Jun 17 '13 at 10:29
Mohammad Al-Turkistany
13.9k4 gold badges49 silver badges130 bronze badges
Only top voted, non community-wiki answers of a minimum length are eligible
