Share Your Experience: Take the 2024 Developer Survey

# Tag Info

### Is every non-recursively-enumerable language RE-hard?

Partial answer here: I think it at least depends on the chosen reduction. For example, consider $H\in \mathsf{RE}$ the halting problem. Then $\overline{H}\notin \mathsf{RE}$, but there is no many-one ...
• 15.7k
Accepted

### Can I reduce a non semi decidable and undecidable language to a semi decidable and undecidable langauge? many-one reduction

It depends on the reduction. Using a Turing reduction, it is possible. For example, any problem $A$ is Turing-reducible to its complement $\overline{A}$, by puting a negation on an answer given by an ...
• 15.7k
Accepted

### NP-hardness of a variation of the bin packing problem

The bin packing problem is strongly NP-hard. That means that even if the sizes are given in unary, the problem is still NP-hard. In your case, your product-bin packing is equivalent to sum-bin packing,...
• 15.7k
Accepted

### Reduction from dominating set to disconnected dominating set

Consider an undirected graph $G = \langle V, E\rangle$, and consider a dominating set $S\subseteq V$ in $G$. If you mean by "$S$ is disconnected" that the subgraph induced by $S$ is not ...
• 2,931

### Is there such a thing as $coW[1]$-hardness?

The paper The Parameterized Complexity of Local Consistency by Gaspers and Szeider discusses coW[1]- and coW[2]-complete problems. This is maybe a starting point.
Accepted

### Prove "Vertex Cover OR Clique" is NP complete

You can easily reduce from clique as follows. First, notice that the clique problem remains NP-hard even if we restrict $k$ to lie in $3 \leq k \leq n$ (because outside this range the problem is ...
• 2,522

### Is the ABC-partition problem NP-hard?

This seems to be the Numerical 3D matching problem. Wikipedia cites a proof of NP-Hardness by Garey and Johnson (problem SP16).
• 29.5k

### if there is a 3/2 approximation algorithm for independent set then there is a 3/2 approximation algorithm for vertex cover?

Try to prove it. Don't just assume "it should be true"; write out the proof in detail. Specify the algorithm for finding a 3/2 approximation for Vertex Cover concretely. Provide a proof ...
• 161k

### reduce independent Set into independent Set of distance 4 between all vertices

For an input to independent set, subdivide each edge twice, add a new vertex that is incident to every subdivision-vertex. Now, the distance between two vertices in the new graph is 4 if and only if ...
• 16.5k

### "Term Rewriting and All That" - Exercise 2.3

I don't know what is the definition for a reduction to be decidable. I would expect it is one of the following two: Defn 1: $\to$ is decidable iff there is an algorithm $A$ that always halts and, on ...
• 161k
Accepted

### Reduce CNF-SAT to decision problem

It is not clear in your solution why treating clauses as groups helps. Note that a satisfying assignment should induce a set of groups and vice versa. Hint: a non direct reduction (but you can start ...
• 2,931
Accepted

### EXP reduction to show NEXP-completeness

The complete statement about completeness for complexity classes is "Problem A is complete for complexity class B under C-reductions." In many cases it is clear from the context what notion ...
• 3,113

### $A$ and $B$ two decision problems.If $A\le\ B$ then $\overline{B}\le\overline{A}$ is true?

The claim is false. There are several ways to show it. Note that if $\overline{B} \leq_m \overline{A}$, then $B\leq_m A$ (this is what you've shown). Hence, if by contradiction the claim is true, then ...
• 2,931

### Invertability of Karp reductions

The Berman-Hartmanis isomorphism theorem [1, p.312] says that poly-time invertible reductions exist between any two paddable NP-complete languages: If two NP-complete languages $A$ and $B$ are ...
• 930
Accepted

### How does the half-integer spanning-tree problem contain the TSP?

Reduction from Hamiltonian Cycle (which is just a special case of TSP anyway): Take an unweighted graph $G$ and make into a complete weighted graph $G'$ by adding a heavy edge (say, $\ell(e) = 2n$) ...
• 1,058

### Graph Coloring Decision Problem Reduction to Prove NP-Complete

SAT can be reduced to 3-SAT in a straightforward way (the Tseitin transform), and you seem to be aware that 3-SAT can be reduced to 3-coloring (e.g., https://www.cs.toronto.edu/~lalla/373s16/notes/...
• 161k
1 vote

• 2,931
1 vote

### Help understanding the proof that $L = \{ \langle M \rangle \mid M \text{ is a TM that accepts the input string } 101\}$ is undecidable

As you know, a Turing reduction from $L_1$ to $L_2$ (i.e. $L_1 \leq_T L_2$) means that if we can decide $L_2$, then we can also decide $L_1$. In general to show $L_1 \leq_T L_2$, we construct a ...
1 vote
Accepted

### Proving $A_{TM}$ is mapping reducible to certain language

For a reduction $f$ to be computable, there must be a TM that for all inputs $y$ halts with $f(y)$ written on its tape. The reduction you suggested is indeed computable. Here, your input $y$ is ...
• 2,931
1 vote

### Showing this scheduling problem is NP-hard

The problem is strongly NP-Hard as it can be seen by reducing from the $3$-partition problem: given a set $X = \{ x_1,\dots,x_{3n} \}$ of $3n$ positive integers, is there a partition of $X$ into $n$ ...
• 29.5k
1 vote
Accepted

### Is this considered a vertex cover?

Yes, this is a vertex cover (VC). By definition, a vertex cover of a graph G=(V,E) is a subset of nodes $U\subset V$ such that $\forall \ e \in E \ \exists u \in U$ such that $e$ is incident in $u$. ...
• 898
1 vote
Accepted

### Reduction from MAX-3-CUT to MAX-CUT

We want to use a $\textsf{MAX-CUT}$ algorithm to solve the $\textsf{MAX-3-CUT}$ problem. Therefore we need to transform our original graph $G$ into a new graph $G'$ in such a way that finding a max-...
1 vote
Accepted

### How to reduce $k$-oriented problem to max flow problem?

A similar solution to the one given here works here as well. The following is the reduction (non-highlighted statements are directly taken from Steven's answer): Given $G=(V,E)$, create a directed ...
• 6,187

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