# Tag Info

3

Sometimes we insist that the three literals in a 3SAT clause belong to different variables. This ensures, for example, that a random assignment satisfies a clause with probability exactly $7/8$. The translation $x \lor y \lor y$ doesn't satisfy this condition, but the other one does.

2

As I understand, your problem is a decision problem defined as such: Independant set with fixed vertex (ISFV): Input: a graph $G = (V, E)$, a vertex $u \in V$, an integer $k$. Question: is there an independent set of size $k$ containing $u$? Independent set (IS) is defined as: Input: a graph $G = (V, E)$, an integer $k$. Question: is there an independent ...

2

Let $S$ be any language in $\mathsf{P}$. You are looking for a function $f$ with the following properties: $f$ can be computed in polynomial time. If $x \in S$ then $f(x) \in A$. If $x \notin S$ then $f(x) \notin A$. Since $S$ is in $\mathsf{P}$, we can determine whether $x \in S$ in polynomial time. Therefore, the reduction $f$ can work as follows: ...

2

Suppose we have a solution to the longest path problem, longest-path, in which given a graph G, and an integer k, we need to decide if G has any (simple) path of k edges. Then to solve the Hamiltonian-path problem, HAM-PATH, we could use longest-path with k=|G|-1. This means, HAM-PATH is polynomial time reducible to longest-path. \begin{aligned} i.e., ...

1

As mentioned in the comments, this reduction is incorrect because it is necessary to have equivalence. While we may have 3-SAT => Half-SAT we do not have !3-SAT => !Half-SAT or Half-SAT => 3-SAT (the contrapositive). A proper reduction would need to do something like so: Add m + 1 clauses (y or y or y) Add a contradictory clause (y or not y) Now ...

1

Your algorithm doesn't return a $k$-clique. Simply consider a connected graph $G$ that is a proper supergraph of a $k$-clique, and an isolated vertex $x$. Your algorithm with input $G+x$ returns $G$. You can solve your problem as follows: While $\exists$ a vertex $v$ of $G$ such that $B(G-v)$ returns true: Delete $v$ from $G$ Return $G$. Let $G^* = (V^*,... 1 Using the definition of reduction,$x\in L_1\iff f(x)\in L \iff x\in L_2$And thus$L_1=L_2\$.

Only top voted, non community-wiki answers of a minimum length are eligible