New answers tagged reductions
1
Your reduction actually shows that $L_m$ is not co-RE. Indeed, if $L_m$ were co-RE, then your reduction shows that $L_u$ is also co-RE. However, $L_u$ is known to be RE but not recursive, hence cannot be co-RE.
Similarly, you can show that $L_m$ is not RE, by reduction from the complement of the halting problem: given an instance $(M,w)$ of $L_u$, create a ...
0
Let $T = (V,d,k)$ be an instance of Metric-TSP, where $V$ is a vertex set, $d: V\times V \rightarrow \mathbb{R}_{\geq 0}$ is a distance with triangle inequality, and $k\in \mathbb{R}_{\geq 0}$.
Suppose that $T$ is a positive instance of Metric-TSP (i.e. there exists a tour with total length $\leq k$. Then $T$ is also a positive instance for your variant (...
1
Based on Thinh D. Nguyen's answer I think I have a simpler (to understand) reduction showing the problem is at least as hard as SET COVER.
The core of the construction is a one-way deduction relationship $a \to b$. Split $a$ into two variables, $a$ an $a'$ and add equations:
$$\{a, a'\}, \{a, a', b\}$$
Then given either $a$ or $a'$ we can deduce $b$, but ...
1
Yes, it is $NP$-complete even if $d=4$.
Note that unless $P=NP$, we cannot prove $NP$-completeness for $d=2$ because it is merely the problem of counting the number of connected components of a given graph.
Reduce from Exact-Cover-by-$3$-sets (X3C).
Given an instance of X3C, we construct an instance of our problem as follows.
The set of elements is $E=\{...
0
If you want to reduce Clique directly to 3SAT, you can design a boolean circuit, where the input is a graph and a subset of vertices, and the output is TRUE if that subset is a clique and FALSE otherwise.
If the graph has N vertices, you need:
N variables, one for each vertex, which is TRUE if it is part of the subset and FALSE otherwise.
N * (N - 1) ...
Top 50 recent answers are included
