97
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 ...
94
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 ...
48
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; ...
41
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 ...
36
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 ...
34
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
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 $...
28
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 (...
27
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.
26
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,...
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
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
20k4 gold badges54 silver badges136 bronze badges
25
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 ...
25
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 ...
23
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 ...
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 ...
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 ...
21
For a given graph $G$ and an integer $k\ge 1$, the $k$-th power of $G$, denoted by $G^k$,
has the same vertex set such that two distinct vertices are adjacent in $G^k$ if their distance in $G$ is at most $k$. The $k$-th power of split graph
problem asks if a given graph is the $k$-th power of a split graph.
For $k=1$, the problem solvable in linear time....
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,9152 gold badges23 silver badges34 bronze badges
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
Kaveh is correct in saying that all of the "natural" NP-complete problems are easily seen to be complete under (uniform) $\mathrm{AC}^0$ reductions. However, one can construct sets that are complete for NP under logspace reductions that are not complete under $\mathrm{AC}^0$ reductions. For instance, in [Agrawal et al, Computational Complexity 10(2): 117-...
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
I think there are lot of similar problems. Here are two in vertex version and one in edge version:
1) Does a given graph have an independent feedback vertex set? (we don't care about the size of the set).
This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in
Garey, Johnson & Stockmeyer.
2) Does a given graph have a ...
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
20k4 gold badges54 silver badges136 bronze badges
18
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 sum described in the top answer to the linked question, but with the target range encoded as the largest two primes instead of given separately. The definition ...
18
Like Turing reductions, many-one reductions came into complexity theory from computability/recursion theory literature. Cook and Karp reductions are natural complexity theoretic versions of similar existing reductions in computability.
There is a intuitive way of explaining many-one reductions: it is a restriction of Turing reductions where we can ask only ...
18
Group Isomorphism $\leq_m$ Graph Isomorphism $\leq_m$ Ring Isomorphism. Also Integer Factoring $\leq_m$ Ring Isomorphism [Kayal and Saxena]. Also Graph Automorphism $\leq_m$ Graph Isomorphism.
Not only are there no known reductions the other way, but there is provably no
$\mathsf{AC}^0$-reduction from Graph Iso to Group Iso [Chattopadhyay, Toran, and ...
Only top voted, non community-wiki answers of a minimum length are eligible
