New answers tagged reductions
1
Here is an example. Consider the problem of vertex cover. An instance of vertex cover consists of a graph $G$ and an integer $k$. This is the domain $D$. You can easily come up with a one-to-one encoding $e\colon D \to \Sigma^*$ such that (i) you can recognize whether a string is in the range of $e$ in polynomial time, (ii) given such a string, you can ...
1
Probably you can get your answer from here: Reducing independent set to triangle-free subgraph
Basically in order to prove that $TFS$ is NP-complete you can just check the first proof in the link's answer. Given a graph $G$ with an independent set $k$, there exists a $G'$ with a $TFS$ of size $|V|+k+1$.
0
If $A \leq_P B$ then since $P \subseteq P/\mathit{poly}$, also $A \leq_{P/\mathit{poly}} B$. This means that there is a function $f \in P/\mathit{poly}$ such that $x \in A \leftrightarrow f(x) \in B$. Since $f \in P/\mathit{poly}$, for every $n$ there is a polynomial size circuit $C$ that computes $f(x)$ for $x$ of length $n$. The circuit needs to have some ...
0
Given $a,b,c\in\mathbb Z$ the quadratic program
$$\exists x,y\in\mathbb Z$$
$$ax^2+by-c=0$$
is known to be $\mathsf{NP}$-complete by https://www.sciencedirect.com/science/article/pii/0022000078900442. If you had no non-linear constraints but a non-linear objective it is called a linear program having a non-linear objective (for example a convex objective). $\...
2
It is called contraposition :
$f(x) \in B \Rightarrow x \in A$
is equivalent to
$x \notin A \Rightarrow f(x) \notin B$.
So, the two statements that you have seen are equivalent as well.
1
Your question is a bit unclear, but let me hazard a guess. Let $L$ be an NP language. According to the Cook–Levin theorem, there is a polynomial time reduction $\phi_L$ from $L$ to SAT, that is, $\phi_L$ is a polynomial time function that satisfies $x \in L$ iff $\phi_L(x) \in \mathrm{SAT}$. You are asking why $\phi_L$ is injective.
Roughly speaking, $\phi_L(...
2
Suppose your original graph $G$ has a Hamiltonian cycle $C$.
Then the cost of the tour induced by $C$ in the new graph $G'$ you defined is indeed $0$ and conversely, any TSP tour of cost $0$ can only use edges of cost $0$ as you did not introduce any edges with a negative cost.
Adding the loops does not change this, so the reduction works out if we are ...
Top 50 recent answers are included
