New answers tagged reductions
2
While @nir shahar's answer is not wrong, your question is about the complexity of TAUTOLOGY when we have no assumptions on the structure of the formula. In the special case of Conjunctive Normal Form (CNF, a AND of OR clauses), you can solve TAUTOLOGY in polynomial time, as Shahar says. However, there are other special cases for which TAUTOLOGY is co-NP-...
3
As you correctly spotted, the reduction can be implemented in polynomial time, and the blowup in the formula size is indeed linear.
The reduction is also correct, with the caveat mentioned in item 2.
It's not trivial to show, but we'll go at it slowly.
So first, let's assume we allow this construction also for 2 literals. As for 1 literal clauses -- we can ...
1
I think one of an important parts of reduction for languages like Clique and Subset-sum is the integer we have given next to the input. That is $k$ for Clique which tells us which size of the clique we are looking for and $d$ in Subset-sum that tells us the sum of a collection of numbers.
I have drawn little pictures for you to see how this works.
For ...
1
The reduction from $Clique \leq_P SubsetSum$ is incorrect. Take a graph $G$ with four vertices $(v_1, ..., v_4)$, edges $(v_1, v_2), (v_3, v_4$) and let $d = 4$. Then $A = \{1,1,1,1\}$ (assuming $A$ is a multiset). Clearly there is a subset in $A$ whose sum is 4 but there is no clique of size 4 in $G$.
As for the reduction $SubsetSum \leq_P Clique$, your ...
2
Intuitively $A \le_p B$ means that a polynomial-time algorithm for $B$ can be used to solve $A$ in polynomial-time, not vice-versa.
That said $f$ is not required to be surjective, think for example of $A=\Sigma^*$ and $B=\{0,1\}$. Suppose that $f(x) = 0$ (i.e., $f$ is the constant function). Simulate the algorithm with $y=1$ and notice that it will reject ...
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
Alright, we are given a language $C \in \mathrm{P}$ and a language $A \in \mathrm{NP}$, and we are promised that $C \leq_p A$. What can we conclude?
First a side remark: The reduction $C \leq_p A$ tells us very little since we know $C \in \mathrm{P}$. The only extra information we get is that if $A$ is empty, then so is $C$, and if $A = \Sigma^*$, then $C = \...
2
Regarding the first part.
Answer 1 is incorrect. Consider the graph $G = (\{1,2,3,4,5,6\}, \{(1,2), (1,3), (2,3), (3,4), (4, 5), (4,6) \})$. The maximum degree of $G$ is $3$ but the degree of $x_{(3,4)}$ in $\widetilde{G}$ is $4$.
Answer 2 is correct. Consider an edge $e=(u,v)$ of $G$. The number edges distinct from $e$ that are incident to $u$ (resp. $v$) ...
2
Let's check these in reverse order.
Question B: your reasoning looks good as it demonstrates that both (1) and (2) are not strong enough. The choice (4) is a possible bound, but it's not as tight as it can be. Your example is extremal in a sense that you can't make the degrees any larger, meaning that your bound is, as the question asks, "closest ...
2
Option 1 is odd. We don't know whether a polynomial algorithm can be constructed. The "passing all the neighbors at a distance of less than 6 from each vertex in $G$" is unclear. Any algorithm solving the TSP problem must visit all vertices. Therefore it must also visit all neighbors of each vertex and, in particular, all neighbors at distance less ...
2
1 is wrong. The problem is NP-Complete by an easy reduction $f$ from the clique problem.
Let $\langle G,k \rangle$ with $G=(V,E)$ be an instance of (the decision version of) clique. If $k$ is odd then the reduction is the identity function, i.e., $f(\langle G,k \rangle)=\langle G,k \rangle$. Otherwise create a new graph $G=(V', E')$ with $V' = V \cup \{v\}$...
1
Saying that a "language reaches the state of reject" is meaningless. Languages don't have states. Turing machines and automatons do.
That said, your language is undecidable. Given $\langle M,w \rangle$ you can compute the pair $\langle M',w \rangle$ where $M'$ behaves exactly as $M$ except for the following: every transition that halts the machine ...
2
From what I understand in the question, there is a language that accepts Turing machines that go into an endless loop.
We do not say a language "accepts" something. Rather the language contains all pairs of turing machines and words, where the TM runs forever (which I take "infinite loop" to mean) on the word.
Also, note that you can ...
2
To see whether a "reduction is correct and well-defined", first look at the definition: what is a reduction? In this case, you require a so-called Karp reduction or a polynomial-time reduction from Edge-Coloring to Vertex-Coloring. In particular, it must hold that (i) the process runs in polynomial time and (ii) an instance $G$ of Edge-Coloring has ...
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$. ...
5
The main "key" here is to understand how a formula is structured. Assuming the formulas of TAUTOLOGY are in CNF, then there exists a polynomial algorithm:
Let $\varphi=\bigwedge_{i=1}^{k}\limits C_i$ where each $C_i$ is described as an $\lor$ of multiple literals.
Notice, that in order for an assignment $\rho$ to satisfy $\varphi$, we need $\rho$ ...
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
$P$ is closed under complement. The rest is up to you.
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$) ...
1
The "key" here is to make $f$ construct a new machine $M'$ that will contain all of the primes assuming that $w\notin L(M)$, and otherwise, there will be at least one prime it rejects.
Now, the reduction $f$ will work by taking $\langle M, w\rangle$ and outputting the following TM $M'$:
On input $z$, run the following:
Emulate $M$ on $w$ for $|z|$ ...
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
I assume that by "verses" you mean boolean formulas.
The language is definitely in CO-NP since a "no" certificate is a satisfying assignment.
Currently we don't know whether FALSE is in P nor whether it is in NP.
0
You should make $c=|2T-sum(S)|$. Show that the reduction then holds no matter what $T$ is.
0
The total number of tile pairs is finite, the reason is: The number of the states of Turing machine M, the length of its input string w and the number of the tape alphabet are all finite, thus the number of their combinations, which are basically the tile pairs, is finite.
0
Here a possible function $f$ that provides the reduction from $L_1$ to $L_2$.
$$
f(x) = \begin{cases}
\varepsilon & \mbox{if $x=a$} \\
b & \mbox{otherwise}
\end{cases}.
$$
4
First, note that Sipser says ""If M's language isn't empty, N will accept every input".
Let us first prove this statement:
Assume $L(M) \neq \emptyset$.
Then there exists some $x \in L(M)$. Because $L(M) \subseteq \Sigma^*$ we have $x \in \Sigma^*$. Then because $s_i \in \Sigma^*$ and $\Sigma^*=\{s_0, s_1, s_2, .... \}$, there exists an $i^*...
Top 50 recent answers are included
