New answers tagged np-complete
1
To show that Vertex Cover and 3SAT is "equivalent", you have to show
that there is a 3SAT satisfaction if and only if there is a k vertex cover in the graph constructed in the reduction step.
Assuming you are familiar with how the reduction is done, (if not ,refer to the document).
Since you only asked about
how this setup proves that if there exists a k-...
1
Hint: let $A$ be a NP-complete language and $B=\Sigma^*$. Then $A \cup B = \Sigma^*$. Is $B$ the complement of $A$? Does it belong to coNPC?
1
Does this always work on larger matrices with 2*n rows and 2*n+1 columns where n is the number of variables? (I think it may need non-redundant (linearly independent?) rows.)
It works but since there are assignments other than -1 and 1, how will you use the row echelon form to make any conclusions about the 1-in-3 SAT instance?
Two cases:
Case 1: The 1-...
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
Membership of your problem in $\mathsf{NP}$ is trivial. To prove that it is also $\mathsf{NP}$-hard consider an instance of (the decision version of) independent set consisting of a graph $G=(V, E)$ with $|V|=n$ and of an integer $k$.
Construct the graph $H = (V', E')$ where $V' = V \cup \{ x_{u,v} \, : \, (u,v) \in E \}$ and $E' = V' \times V'$.
For each $...
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+...
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.
2
Your problem is NP-hard. To see this, you can reduce it from the minimum test cover (or test collection) problem: given a set $X$ of $\ell$ elements and a collection $C = \{C_1, \dots, C_k \}$ of $k$ subsets of $X$, find a minimum test cover for $X$ and $C$, i.e., a subset $C'$ of $C$ that has minimum size and satisfies the following property: for every pair ...
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
We will reduce from 3COL, which is the following problem: Given a graph, is it 3-colorable?
Given a graph $G=(V,E)$, we construct a new graph $G'$ on $V \times \{1,2,3\}$, whose edges are
$$
\{((i,a),(j,a)) \mid (i,j) \in E, a \in [3]\} \cup \{((i,a),(i,b)) \mid i \in V, 1 \leq a < b \leq 3 \}.
$$
In words, we take three copies of $G$, and connect all ...
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
Your first problem is $\mathsf{NP}$-Complete. Membership to $\mathsf{NP}$ is trivial. To see that it is $\mathsf{NP}$-hard, you can reduce it from Subset Sum. Let $\langle S_1, W_1 \rangle$ be an instance of Subset Sum. Define $S_2$ as the multiset obtained by multiplying each number in $S_1$ by $100$, and $W_2 = 100 W_1$. The instance for your problem is $\...
2
(other than bounding the complexity of verification to polynomial time).
This is exactly the reason the problems can be solved in exponential time. An algorithm can simply run the verification algorithm for all possible certificates to see if any one of them is a valid "solution". There are only exponentially many certificates since the definition of $NP$ ...
3
Intuitively, the difficulty of all $\mathsf{NP}$-Complete problems is related: solving any single $\mathsf{NP}$-Complete problem in time $O(t(n))$ immediately yields an algorithm for any other $\mathsf{NP}$-Complete problem with a running time of $O(t(\mbox{poly}(n)))$. This shows, for example, that either all $\mathsf{NP}$-Complete problems admit polynomial-...
Top 50 recent answers are included
