New answers tagged np-complete
1
Your algorithm $Z$ doesn't decide $A$. If the input is in both $A$ and $B$, then it returns "no" even though the correct answer is "yes." The error can't be fixed, since it's generally impossible to deduce whether an input is in $A$ if you only know its membership status in $B$ and $A \setminus B$.
1
Take $B=\Sigma^*$. Obviously, $A\setminus B=\emptyset$ is not NP-complete. I'm not sure how concatenation has anything to do with set subtraction, but obviously, concatenating $B=\Sigma^*$ to $A\setminus B=\emptyset$ won't yield $A$ back, since $\Sigma^* \emptyset=\emptyset$ as $\emptyset$ doesn't contain any words.
1
Let $C$ be any language in $NP \setminus \{ \emptyset \}$. Notice that such a $C$ exists (e.g., $C = \Sigma^*$).
The claim "if $A$ is $NP$-Complete and $B$ is in $P$ then $A \setminus B$ is $NP$-complete" is false (regardless of whether $P=NP$).
To see this pick $B=\Sigma^*$. Then $A \setminus B = \emptyset$.
Since there is no polynomial-time ...
2
We start with the assumption that there is a non-trivial language $A$ which is in $\mathrm{coNP}$, but not $\mathrm{coNP}$-complete. We note that it is rather straight-forward to see that if $\mathrm{P} = \mathrm{coNP}$, then every non-trivial language in $\mathrm{coNP}$ is $\mathrm{coNP}$-complete. Conversely, Ladner's theorem states that if $\mathrm{P} \...
2
Let $L\in NP$. Thus, $L\le_p A$. Since $A\in coNP$, then $L\in coNP$. Hence, $NP\subseteq coNP$.
Now, let $L\in coNP$. Thus, $\overline{L} \in NP$ and therefore $\overline{L}\le_p A$. From reduction properties, we know that $L\le_p \overline{A}$ holds as well. Now, since $A\in coNP$ then $\overline{A}\in NP$. Hence, $L\in NP$, and therefore we get that $coNP\...
0
Let $X = \{ x_1, x_2, \dots, x_n \}$ be the (multi-)set of elements in your subset-sum instance and let $t$ be the target value.
Create the undirected graph $G=(V,E)$ where $V=\{a,b\} \cup X$ and $E = ( \{a,b\} \times X) \cup \{(a,b)\}$.
The weight of edge $(a, x_i)$, for $x_i \in X$, is $x_i$. The weight of edge $(b, z)$ for $z \in \{a\} \cup X$ is $0$. ...
2
if a problem is in $NPH$ then it is also in $NPC$
This statement is incorrect. A language is in $NPC$ if it is in $NPH$ and it is in $NP$.
Answer 4 is incorrect as well since that would imply that any language $L\in NP$ can be reduced to $F$, hence $L\le_p F$ and since $F\in coNP$ then $L\in coNP$. Hence, $NP\subseteq coNP$. Its not hard to show the other ...
0
It is 2 that is correct. Here is an alternative explanation:
Notice that any language in $P$ has to be $P$-complete. In addition to that, if $P=NP$ then $NPC=P$-complete. Combining both arguments implies that $NP=P=P\text{-complete}=NPC$. Therefore, if $NP\neq NPC$ then $P\neq NP$.
1
This question refers to a specific transformation that you have seen during the course but we are not given, so we can only guess.
A standard transformation from a SAT clause $C$ to a collection of 3-SAT clauses is as follows:
If $C$ already contains $3$ literals, then $C$ is left unchanged.
If $C$ contains $1$ (resp. $2$) literals, then add $2$ (resp. $1$) ...
2
We don't know whether this is true.
This is true, a certificate is an edge coloring with at most $k$ colors.
This is true. Edge coloring is a well-known NP-hard problem (see here for a reduction from 3-SAT) and hence there is Karp reduction from every problem in NP to it. In particular there must also be a reduction from vertex coloring (which is NP-hard) ...
1
For (3), you are correct, i.e., the problem is NP-complete. As a side note, you might also like to know that you can solve edge coloring by using vertex coloring algorithms by taking the line graph. Note that this in itself does not prove NP-completeness.
For (2), you need to show that if you given a certificate, then you can verify it in polynomial time. ...
1
$L$ is given as part of the input, and can be e.g., $n/2$, where $n$ is the number of items.
Then, iterating over ${n\choose L}={n\choose \frac{n}2}$ is exponential.
Note that it doesn't matter whether $L$ is given in unary or binary, since $n$ is given in unary (as a list of the different items).
3
The reference you should have found is [1], where the authors consider several parameters and also higher dimensional knapsack problems (see e.g., Table 1 for a list of running times for different parameters). A non-paywalled version is on arXiv.
[1] Gurski, Frank, Carolin Rehs, and Jochen Rethmann. "Knapsack problems: A parameterized point of view.&...
1
Theorem. Any finite language L is in P.
Proof.
Let M be a Turing machine which has all strings of L on its tape. When given an input it checks whether the input is on its tape. This is O(1) time clearly.
Theorem. If and only if P=NP, then every L in P (including thus all finite languages) are NP-Complete.
Proof.
Recall that a language is NP-Complete iff ...
0
Regarding 1. Consider a CNF-SAT formula $\phi$ with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $C_1, \dots, C_m$.
For $i=1,\dots,n$ define $s_{i,0} = \{ C_j \mid \overline{x}_i \in C_j\}$ and $s_{i,1} = \{ C_j \mid x_i \in C_j\}$.
The formula $\phi$ is satisfiable if and only if it is possible to select one $s^*_i \in \{s_{i,0}, s_{i,1}\}$ for each $i$ ...
3
Your idea is in a good direction. To complete this proof, you will need to note a few things, and explain why they are not problems (or how to fix them):
The new machine will only do one oracle call at the end. That means, that at any time that our original TM did an oracle call, it wont get an answer!
We need to "save up" and "remember"...
1
You are right that that doesn't prove the algorithm is polynomial, as it just gives the certificate. But it is very easy to see that (for example with a program in a C-like language, given a reasonable representation of the graphs) the check is very easy to do (is polynomial).
The part of coming up with a polynomial verifier given a reasonable certificate (...
Top 50 recent answers are included
