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
