New answers tagged np
3
The number of k-tuples of vertices in a graph with $n$ vertices are: $^nC_k$. You can iterate through each possible k-tuple and check in $O(k^2)$ time whether the given k-tuple forms a clique. For any fixed natural $k$, the number $^nC_k$ is $O(n^k)$, and hence you can check whether a graph has $k$-clique in $O(k^{2}.{^n}C_k)$; the problem would be in $P$.
...
5
You are correct.
3-clique can be solved in $O(n^3)$ time, whereas 3-coloring is NP-hard.
So there can be no "poly-time reduction" from 3-coloring to 3-clique, unless $P=NP$.
5
Let me recap the proof. We are given a sparse NP-hard language $A$: for each length $n$, there are at most $n^c$ strings of length $n$ in $A$.
For a satisfiable CNF $\varphi$, let $a(\varphi)$ be the lexicographically first satisfying assignment for $\varphi$. We consider the NP language $B$, which consists of all pairs $(\varphi,w)$ such that $\varphi$ is ...
2
For the first question: This is an open problem. If $\mathsf{P} \neq \mathsf{NP}$ then the answer is no: the decision version of 3-SAT is $\mathsf{NP}$-Complete, while Primality is in $\mathsf{P}$, the means that a Karp reduction from 3-SAT to Primality would imply $\mathsf{P}=\mathsf{NP}$.
For the second question:
Primality is in $\mathsf{P} \subseteq \...
2
Let $\langle G=(V, E), k \rangle$ be an instance of Independent Set, and call $n=|V|$.
Let $N$ be a set of $n+1$ new vertices (not in $V$), and construct a new graph $G' = (V', E')$ where $V' = V \cup N$ and $E' = E \cup (N \times V)$.
If $G$ has an Independent Set $S$ of size at least at least $k$ then $G'$ has a Triangle-Free set $S'$ of size at least $n+...
2
This problem is NP-hard (and in addition hard to approximate and W[1]-hard), because maximum independent set can be reduced to it. Reduction: Each variable represents a vertex and each clause represents an edge.
3
The result you are trying to prove is known as Mahaney's theorem. It is covered by textbooks on complexity theory, and in many online lecture notes.
The proof in Jonathan Katz' lecture notes indeed uses LEXSAT.
0
A proof of "yes" instance means providing a solution. Providing a solution is providing a valid input. By definition, it can be verified in time and space polynomial relatively to the input, or else it is not a problem in NP.
It is unknown whether all proofs of "no" instances are verifiable in polynomial time and space (the difference between NP and Co-NP)....
1
The decision problem "Is the first bit of the input a 0?" can be solved in constant time and space - without reading the whole input.
Given that a Turing machine head moves right one step at a time, a Turing machine head can only read a polynomial amount of the proof in polynomial time.
While you could define proofs to exceed a polynomial length, only a ...
3
Such a reduction is described in Appendix B of Régis Barbanchon, On unique graph 3-colorability and parsimonious reductions in the plane. Barbanchon attributes it to previous work ([9] in the bibliography). Elsewhere, I have seen an attribution to Schaefer's celebrated paper in which he proves his famous dichotomy theorem, among else giving a reduction from ...
4
Yes, a 3-SAT formula $\phi$ can be transformed into a 1-in-3 SAT formula $\phi'$ while preserving the number of satisfying assignments. To avoid ambiguities I will use "$\vee$" between literals of a 3-SAT clause, and commas between literals of a 1-in-3 SAT clause.
Let me preliminarily show that, given two literals $a$ and $b$, we can simulate a new type of ...
2
Consider the following CNF:
$$
(a \lor \lnot b) \land (\lnot a \lor b) \land (a \lor b).
$$
It has a unique satisfying assignment, $a=b=\top$, which satisfies the last clause twice. However, if you remove the last clause, then you get another satisfying assignment, $a=b=\bot$.
1
Thanks to comments by Yuval Filmus, I understand that my question does not make sense as Karp reductions are defined for decision problems. Since Cook reductions allow more freeness, it makes sense to talk about a Cook reduction from a decision problem to an optimization problem, but this is not true for Karp reduction.
2
Suppose that $f$ is injective. Consider the following nondeterministic machine for $L$: on input $w$, the machine guesses $z$ of size between $|w|^{1/k}$ and $|w|^k$, and verifies that $f(z) = w$. Since $f$ is injective, if $w \in L$ then there is exactly one witness $z$, and so $L \in \mathsf{UP}$.
Since $L$ is always in $\mathsf{NP}$ (using the very same ...
1
Assume that the integer $k$ of the (decision version of the) independent set instance $G$ you are reducing from is larger than $1$ (the case $k \le 1$ is trivial).
Let $G'$ be the graph of the corresponding instance of strongly independent set.
As it is written in your solution notes, all the additional vertices are connected to one another with a clique. ...
Top 50 recent answers are included
