Skip to main content
Share Your Experience: Take the 2024 Developer Survey
6 votes

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 ...
Nathaniel's user avatar
  • 15.7k
5 votes
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 ...
Nathaniel's user avatar
  • 15.7k
3 votes
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,...
Nathaniel's user avatar
  • 15.7k
3 votes
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 ...
Bader Abu Radi's user avatar
3 votes

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.
Tim Seppelt's user avatar
3 votes
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 ...
Tassle's user avatar
  • 2,522
2 votes

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).
Steven's user avatar
  • 29.5k
2 votes

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 ...
D.W.'s user avatar
  • 161k
2 votes

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 ...
Pål GD's user avatar
  • 16.5k
2 votes

"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 ...
D.W.'s user avatar
  • 161k
2 votes
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 ...
Bader Abu Radi's user avatar
2 votes
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 ...
Arno's user avatar
  • 3,113
2 votes

$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 ...
Bader Abu Radi's user avatar
2 votes

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 ...
Neal Young's user avatar
2 votes
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$) ...
Highheath's user avatar
  • 1,058
2 votes

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/...
D.W.'s user avatar
  • 161k
1 vote

PSPACE and Polynomial reduction

Regarding 1: choose $C = \{0x \mid x \in A \} \cup \{1x \mid x\in B\}$. Regarding $2$: $B \le_P \emptyset \implies B=\emptyset$ however $\{\varepsilon\} \le_P B \implies B \neq \emptyset$. Regarding $...
Steven's user avatar
  • 29.5k
1 vote

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

No. Take $A = \emptyset$ and $B = \{0\}$. A reduction $f$ from $A$ to $B$ is the function $f(x) = \varepsilon$ since $x \not\in A$ (regardless of the choice of $x$) and $\varepsilon\not\in B$. However ...
Steven's user avatar
  • 29.5k
1 vote
Accepted

Is it possible to find reductions from problems in $\mathsf{NP}$ to SAT based solely on the certificate verification algorithm?

Finding a reduction to SAT is easy but tedious. Write down a description of polynomial-time Turing machine $T$ that checks the certificate (as you have argued in your question, such a Turing machine ...
Steven's user avatar
  • 29.5k
1 vote

Is the Language of all encodings of Turing Machine that at least halts on one input and outputs 0 semi-decidable?

Since it seems like you are really uncertain about your own solution. Let's verify it step by step: 1- A is undecidable. To prove this statement, it is enought to show that there is a mapping ...
Ali Dastjerdi's user avatar
1 vote

Reducing from the complement of the Halting Problem

For the question to be understandable, you should indicate that "a machine does a thing" actually means that "a machine performs some finite computation and then halts". Anyway, ...
Bader Abu Radi's user avatar
1 vote

Show that the language is undecidable

This follows immediately from Rice's theorem. However, if you don't know that theorem yet and you're asked to prove it by an explicit reduction, see oleshkowitz's answer.
Jean Abou Samra's user avatar
1 vote

Show that the language is undecidable

What languages are you familiar with? Are you familiar with the fact that $ALL_{TM}=\{\langle M\rangle : L(M)=\Sigma^*\}$ is not decidable? If so try a reduction from $ALL_{TM}$ where given a machine ...
oleshkowitz's user avatar
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

Fix $\langle M, w\rangle$, and consider the constructed machine $M_x$. It is not hard to see by the construction of $M_x$ that either $M_x$ accepts all its inputs (and that happens when $M$ halts on $...
Bader Abu Radi's user avatar
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 ...
anonymousBeaver's user avatar
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 ...
Bader Abu Radi's user avatar
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$ ...
Steven's user avatar
  • 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$. ...
SilvioM's user avatar
  • 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-...
Bernardo Subercaseaux's user avatar
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 ...
Inuyasha Yagami's user avatar

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