# Questions tagged [reductions]

In computability and complexity, finding mappings between problems that allow solving one problem using a solution of another one. For reduction in programming language theory (e.g. beta-reduction), see [lambda-calculus] or [term-rewriting].

1,295 questions
Filter by
Sorted by
Tagged with
1 vote
26 views

• 141
28 views

### Proving Non-Semi-Decidability of Language L - Seeking Reduction Strategy

I'm working on a problem involving the language 𝐿 = { 𝑤 ∣ time𝑀𝑤 ( 𝑥 ) ≤ ∣ 𝑥 ∣ + 1 for all words  𝑥 }. The language consists of words 𝑤 where the Turing machine 𝑀𝑤 halts within ∣ 𝑥 ∣ + 1 ...
29 views

### Decidability of Turing Machine

The problem is: Argue, whether it is decidable if a Turing machine M halts within 10 steps on any input. The proposed solution: Simulate every input of length less than or equal to 10 on M. If M ...
25 views

### Why do some authors check for "$x \ne w$" in reductions from $A_{TM}$ to $E_{TM}$?

Def.: $A_{TM} = \{<M, w> \mid M$ is a TM and $M$ accepts $w \}$ $E_{TM} = \{<M> \mid M$ is a TM and $L(M) = \emptyset\}$ I found that some authors (e.g. Sipser 2013, 3rd ed.) use an ...
• 123
57 views

### Are these two definitions related to strong NP-hardness equivalent?

Let $P$ be a computational problem whose inputs are integers. Consider the following properties: (a) There exists a polynomial-time reduction from some strongly-NP-hard problem $Q$ to $P$. (b) $P$ is ...
• 6,164
25 views

### If A ∈ coNP, B ∈ NP and $NP \neq coNP$, is it possible to Karp reduce A to B?

If A $\geq_p$B and $B\in NP$, $A\in coNP$, then we can build a Turing machine $M_A$ using $M_B$ machine of B. Input: w We make a new word with a reduction function $f(w)$. Then we run $M_B$ on $f(w)$ ...
• 21
1 vote
58 views

### Reducing the Independent Set Problem to Independent Set for 3-Colorable Graphs

I am exploring a reduction from the general Independent Set Problem to the Independent Set Problem specifically for 3-colorable graphs. The goal is to demonstrate that the maximal independent set of a ...
49 views

### Using reducibility to prove a language that accepts $\lambda$ and either loops or accepts other strings is undecidable

I am new to the reduction style of proof so I am hoping to get some help on this problem. Let $L=\{〈M〉:M$ accepts the empty string and does not reject any string$\}$. Prove $L$ is undecidable. My ...
21 views

### Issues in the proof of $A_{TM}$ reducidability to $𝐸_{𝑇𝑀}$

I'm studying reducidability in Sipser Book and watching his videos, but I couldn't fully understand his proof of $A_{TM}$ reducidability to $𝐸_{𝑇𝑀}$ (p. 218, 3rd ed). Consider this extract: M1 = “...
1 vote
83 views

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

I am doing research into NP-Complete problems and more specifically started looking into the Graph Coloring Decision Problem or the k-Coloring problem, as described here: Given a graph $G = (V, E)$ ...
• 11
38 views

### Satisfiability of a boolean formula with two occurrences of each variable with a special ordering

I am interested in the complexity of a special case of the boolean satisfiability problem: We are given a boolean formula, consisting only of the logical operators $\land$ and $\lor$ (that can be ...
• 160
330 views

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

Is every language $L \notin RE$ is $RE$-hard? Similarly, is every language $L \notin RE \cup coRE$ is $RE$-hard and $coRE$-hard? It seems like a simple question but I can't find an answer. I tried to ...
• 151
40 views

### Polynomial-Time Solvability Through NP-Completeness Reductions

Let A and B be NP-complete problems. Suppose I have established reductions from problem A to problem B and vice versa. Now, considering a specific instance (or set of instances) of problem A that can ...
• 121
1 vote
153 views

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

Instance: An undirected graph $G$ and a positive integer $k$ Question: Does $G$ contain a vertex cover of size $\leq k$ or a clique of size $\geq k$? Obviously, this problem is solved by polynomial ...
55 views

### Reduction from $ALL$ to $DECIDE$

Let $DECIDE=${$<M> :\ M\ halts\ on \ all \ inputs$} and I wish to show its unrecognizable using a reduction from $ALL=${$<M> :L(M)=\Sigma ^*$} using a deterministic turing machine $R$ ...
• 365
1 vote
52 views

### Show 3-colorable graph with hamiltonian cycle is NP-Complete

The language is : $3COLORHC = \{<G> | \text{ G is an undirected 3-colorable graph that contains Hamiltonian cycle} \}$ I was asked to show that this language is NP-Complete. Showing that the ...
• 285
141 views

### Mapping Reduction from HALT?

I've been given a task to determine whether L={〈M〉|M is a TM that loops on the input c (a constant)} is decidable. I can prove co-L is recognizable so I figured a reduction from HALT to co-L would ...
1 vote
36 views

### Can a Code Script be Optimized for Time and Space Complexity Using Logic Gates

let's say that I have a Python script that performs various operations, including data manipulation, conditional logic, and iteration. However, I'm concerned about its time and space complexity ...
78 views

### Is $\{\langle \langle M\rangle, q\rangle\mid M(\varepsilon)$ enters state $q$ infinite times$\}$ not in RE?

I'm trying to use reduction $\overline{HP} \leq L$, but I just can't think of a way to do so. Any help would be appreciated!
24 views

### Reductions trick where you halt and reject after polynomial time

There's a standard trick I've heard about in reductions where you just halt a machine and reject after some polynomial amount of time if it hasn't accepted yet. Can this be applied to nondeterministic ...
25 views

### Effectively universal Turing machines and Turing-completeness?

An effectively universal Turing machine $T$ is a Turing machine for which there exists a recursive reduction $f$ such that $\forall A:U(A)=T(f(A))$, where $A, f(A)$ are finite sequences of symbols (...
• 1,966
29 views

• 243
91 views

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

I am trying the understand the following statement from the book of Grotschel, Lovasz and Schrijver: Here, $\delta(W)$ is the set of edges incident to a set of vertices $W$. They define an ...
• 6,164
94 views

### PSPACE and Polynomial reduction

thanks for your help. This is my first question, so I am very sorry for the bad presentation of the question. I am studying computer science and this is the question I have been asked for the course ...
1 vote
73 views

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

I have proved that $\overline{A}\le\overline{B}$ is true, but I have no idea how to prove or disprove the opposite direction.
• 41
1 vote
84 views

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

I was wondering if a variation of the bin packing problem where the 'size' of a bin is calculated as the product of item sizes in a bin instead of their sum is NP-hard. It seems like it must be, but I ...
• 113
1 vote
44 views

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

The following problem has made me ask this question: Given a boolean formula $\varphi(X)$ decide if there exists a quantification of $\varphi(X)$ with $k$ $\forall$ quantifiers that holds true. ...
• 1,966
1 vote
47 views

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

I need to prove if the following Language is or is not semi-decidable. A := {w ∈ {0,1}^* | there exists an input x on which M_w produces the output 0} Where A is the language of all the encoding w ∈ {...
80 views

• 101
544 views

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

I understand of the existence of Rice's Theorem, however, I want to understand better how this reduction is formed. My professor gives the answer as follows: "By contradiction, assume that $L$ is ...
28 views

### Karp-reduction of Disk Covering Problem

While preparing for final exam, I encountered a (target) problem where you have $M$ lines and $L$ points and you want to answer if it's possible to cover them all using $K$ disks of unit radius (...
• 115
74 views

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

I've been asked to prove that the language $A_{TM} = \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$ is mapping reducible to the language $LOOP-ONE = \{\langle M \rangle \mid M$ is a Turing ...
• 285
Suppose $L_1\preccurlyeq_T L_2$, and $L_1$ is unrecognizable, can $L_2$ be recognizable? With decidability, if $L_1$ is undecidable, then $L_2$ is undecidable, because $L_1$ is the “easier” question. ...