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
1
vote
1
answer
26
views
BPP, probabilistic-poly-time reduction
A language $𝐿$ is in the class BPP if there exists a probabilistic polynomial-
time TM, denoted N, such that: for every $𝛼 ∈ \{0,1\}^∗:$
$$𝛼 ∈ 𝐿 ⇒ Pr[𝑁(𝛼) = 1] ≥
2
/3\\
𝛼 ∉ 𝐿 ⇒ Pr[𝑁(𝛼) = 1] ...
- 145
1
vote
1
answer
203
views
Which class is the language MAX-CLIQUE in?
We define $$ֿ\text{Max-Clique} = \{\langle G, k\rangle: \text{$G$ is an undirected graph, and the largest clique of $G$ has exactly $k$ vertices}\}$$
Is this language in $\text{NP}$ or in $\text{coNP}$...
- 141
1
vote
1
answer
74
views
How do you show Dominating Set is NP Complete
A dominating set of an undirected graph $G = (V,E)$ is a subset of
vertices $C\subseteq V$ such that every vertex $v\in V$ either belongs to $C$ or has a neighbor in $C$. The corresponding decision ...
0
votes
1
answer
27
views
P=NP iff for any two non-trivial languages A, B in coNP, A≤pB and B≤pA
Prove: $\text{P} = \text{NP}$ iff for any two non-trivial languages $A$ and $B$ in $\text{coNP}$, it holds that $A \leq_p B$ and $B \leq_p A$.
The part of assuming the reductions and proving $\text{P}=...
- 141
0
votes
1
answer
24
views
Polynomial reduction function for languages in NPC, reduction from DHP to given language
Given language:
$L = {\{\langle G, e\rangle \mid G = (V, E)} \text{ a graph that contains a directed Hamiltonian path}$
$\text{that passes through edge } e \in E\}$
I want to show $DHP \leq_p L$.
...
- 31
1
vote
1
answer
21
views
Complete language in P∪{C,D}
given: C is a NP-coNP language, D is a coNP-NP language and P is the known time-complexity class.
assumption: NP ≠ coNP.
I need to determine if exists a language B, such that:
a. B ∈ P∪{C, D}.
b. for ...
- 141
0
votes
1
answer
47
views
The number of words that M doesn't accept is finite
I need to show that the following language isn't Turing recognizable:
$$\text{COFINITE}_{TM} = \{\langle M \rangle | M \text{ is a TM and } \overline{L(M)} \text{ is a finite language}\}$$
but I keep ...
- 141
1
vote
1
answer
98
views
set of words w such that M halts on w is decidable
I need to prove that the language following language is not turing-recognizable:
$$\text{dec-haltTM} = \{ \langle M\rangle: \text{$M$ is a TM and the set of words that M halts on is decidable}\}$$
I ...
- 141
0
votes
1
answer
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
...
- 1
0
votes
1
answer
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 ...
2
votes
1
answer
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
5
votes
1
answer
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
0
votes
0
answers
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
1
answer
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 ...
- 157
0
votes
1
answer
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 ...
- 1
0
votes
0
answers
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
1
answer
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
2
votes
0
answers
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
5
votes
1
answer
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
2
votes
1
answer
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
1
answer
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 ...
- 91
2
votes
1
answer
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
0
answers
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
0
votes
1
answer
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
1
vote
2
answers
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 ...
- 11
0
votes
3
answers
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!
0
votes
0
answers
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 ...
0
votes
0
answers
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
0
votes
0
answers
29
views
Optimally converting N-SAT to 1-in-SAT?
The simplest Reduction for 3-SAT to 1-in-3-SAT reduction is as follows:
For each 3SAT clause: $x+y+z=1$
Introduce 4 new variables $\{a, b, c, d\}$ and replace original clause with below 3 clauses:
$R(...
- 745
0
votes
1
answer
50
views
Algorithm for 3-coloring a graph, given a search algorithm that finds a k-colored graph for $k \ge 4$ if one exists, and otherwise returns false
The problem statement is:
Given a search algorithm that finds and returns a k-colored graph for $k \ge 4$ if one exists, and otherwise returns false, show that there exists a search algorithm for 3-...
- 5
0
votes
1
answer
51
views
Reduction mechanism of PSPACE problems to SPACE-TMSAT
To show $\text{PSPACE-completeness}$ of $\text{SPACE-TMSAT}$, we perform a polynomial-time reduction of $\forall L \in \text{PSPACE}$ to $\text{SPACE-TMSAT}$. The language $L$ can be decided by a TM $...
- 243
3
votes
2
answers
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
-4
votes
2
answers
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
2
answers
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
1
answer
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
1
answer
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
1
answer
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 ∈ {...
2
votes
1
answer
80
views
Reducing from the complement of the Halting Problem
Consider the halting problem $HALT_{TM} = \{\langle M, w\rangle: M \text{ is a TM that halts on input } w\}$,
and some undecidable Language $L$ of the form $L = \{\langle M\rangle: M \text{ does a ...
- 21
1
vote
1
answer
82
views
Reduction from dominating set to disconnected dominating set
Consider an undirected graph $G = \langle V, E\rangle$, and a set $S\subseteq V$ of vertices. We say that $S$ is a dominating set, if for every vertex $v\in V$, it holds that $v\in S$, or $v$ has a ...
- 73
1
vote
0
answers
24
views
CNF Horn-renamability to 3-CNF Horn-renamability reduction?
A CNF formula is Horn-renamable if you can invert variables in such a way that each clause has at most one positive literal. There is an algorithm based on a reduction to 2-SAT given in Renaming a Set ...
- 1,966
1
vote
1
answer
119
views
Reduce CNF-SAT to decision problem
Given CNF-SAT reduce it to the following decision problem:
Given n items, m groups (and for each group a set of items) and a ...
- 183
1
vote
0
answers
36
views
Reduction from Hamiltonian path to Tripartite decision problem
I teach a fairly advanced algorithms class to high schoolers and I accidentally presented them with a bunk reduction from Hamiltonian path to the Tripartite graph decision problem.
My attempt involved ...
- 11
3
votes
1
answer
129
views
Can I reduce a non semi decidable and undecidable language to a semi decidable and undecidable langauge? many-one reduction
Let's say a Language L is NON-semi decidable and undecidable. Let's also take the Halting problem H, which is a semi decidable and undecidable language.
Is it possible to reduce L to H in a many-one ...
1
vote
0
answers
110
views
What's the name of the genre of algorithms for efficiently collecting common factors?
I'm working with sparse vectors represented as index (array of unsigned integers) and coefficient (array of floats with the same ...
- 139
0
votes
1
answer
55
views
"Term Rewriting and All That" - Exercise 2.3
I am working through the exercises in the book "Term Rewriting and All That" and got stuck on question 2.3. The question reads: find a reduction $\rightarrow$ on $\mathbb{N}$ such that $\...
- 101
2
votes
2
answers
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 ...
- 306
0
votes
0
answers
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
2
votes
1
answer
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
0
votes
0
answers
22
views
Does valid value in L2 have to be gotten from L1 when we have a Many-One Reduction from L1 to L2
If I am doing a many-one reduction from L1 to L2, since it is described as a total function, does that mean that every possible encoding in L2 should have been achieved from L1 or is it possible that ...
0
votes
1
answer
37
views
Can an unreocognizable language be Turing-reducible to a recognizable language?
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. ...
- 3