98
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 ...
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 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
20.1k4 gold badges55 silver badges140 bronze badges
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$-...
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 ...
answered Feb 6 '14 at 8:04
Mohammad Al-Turkistany
20.1k4 gold badges55 silver badges140 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
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
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
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.
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
20.1k4 gold badges55 silver badges140 bronze badges
19
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 $\mathrm{NP}=\mathrm{RP}$ and $\mathrm{PH}=\mathrm{ZPP^{RP}}=\mathrm{BPP}$; in particular, it is not even known to imply $\mathrm{NP}=\mathrm{coNP}$. (However, all ...
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
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 ...
18
The first problem comes to my mind is the 2-path problem (or more generally k-path problem). Given $(s_1,t_1)$ and $(s_2,t_2)$, find two disjoint paths from $s_1$ to $t_1$ and $s_2$ to $t_2$, respectively. The problem is NPC for directed graphs but polynomial-time solvable for undirected graphs (although not trivial).
18
(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-Colorability. Inf. Process. Lett. (IPL) 87(1):7-12 (2003)
18
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)$-partite graphs. It can, however, accept some graphs rejected by CLIQUE: graphs $G$ with $\omega(G) < k$ but $\chi(G)\geq k$ (so-called "non-perfect" graphs). The ...
17
A sketch of a possible reduction to prove that it is NP-complete.
Informally it starts from a modified 3SAT formula used to show that 3SAT is ASP-complete (Another Solution Problem), and "follows" the standard chain of reductions 3SAT=>DIRECTED HAMCYCLE => UNDIRECTED HAMCYCLE => TSP
Start with a 3SAT formula $\varphi$ with $n$ variables $x_1,...x_n$ and $m$...
Only top voted, non community-wiki answers of a minimum length are eligible
