# Tag Info

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