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].

Filter by
Sorted by
Tagged with
0 votes
1 answer
32 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
1 answer
803 views

Show that a subproblem of Sparse Subgraph is $\mathcal {NP}$-Complete

I want to show that a subproblem of the known, $\mathcal {NP}$-Complete, Sparse Subgraph problem is also $\mathcal {NP}$-Complete. Sparse Subgraph problem: Input: Undirected graph $G(V,E)$, two ...
1 vote
2 answers
29 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 ...
9 votes
2 answers
346 views

Is the ABC-partition problem NP-hard?

In the ABC-partition problem, there are three sets $A, B, C$ with $m$ positive integers in each. The sum of all integers is $m T$. The goal is to construct $m$ triplets with the same sum $T$, each of ...
0 votes
3 answers
66 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
18 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 ...
4 votes
1 answer
526 views

How to encode reachability in a graph with walls as a SAT problem

Suppose we have a graph that represents a grid of cells. We are given a cell to start in and a cell that's the destination. There are cells that we cannot enter and they are known as walls. Finally we ...
0 votes
0 answers
23 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 (...
0 votes
0 answers
17 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(...
0 votes
1 answer
36 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-...
0 votes
1 answer
31 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 $...
1 vote
1 answer
58 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 ...
1 vote
1 answer
72 views

How do I go about creating a mapping reduction?

So I understand what a mapping reduction is and how to create them for simpler problems such as a reduction from the set of even numbers to set of odd numbers however, seemingly more complicated ...
0 votes
1 answer
104 views

How to prove that $L_{D}\leq L_{U}$?

I have the following two languages: $$ L_{U}\triangleq\left\{ \langle M,x\rangle\,:\,M\text{ accepts }x\right\} ,L_{D}\triangleq\left\{ \langle M\rangle\,:\,M\text{ accepts }\langle M\rangle\right\} $...
0 votes
1 answer
51 views

$L_1= (1$ { $0, 1$ }$^∗) \cup ${ $0x | x \in L$} is NP- complete

If L is NP-complete then how can I prove that $L_1$: $L_1= (1$ { $0, 1$ }$^∗) \cup ${ $0x | x \in L$} is also NP- complete. My thoughts: A reduction from (for example) SAT to L can be converted to a ...
0 votes
2 answers
109 views

Is a language semi-decidable iff it is reducible to ATM?

Thank you. I see how it makes sense going in the opposite direction but i need help proving that this is true. Below is the definition of ATM. ATM={<M,w>| a TM, M accepts w} The question from my ...
-4 votes
2 answers
77 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 ...
3 votes
1 answer
98 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
2 answers
67 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.
2 votes
2 answers
199 views

How complement of ETM is semidecidable

If ETM = {<M> ∣ M is a Turing Machine and L(M) = ∅}, how can I prove that the complement of ETM is semi-decidable?
0 votes
1 answer
194 views

Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable

I am absolutely stumped on this one. I am unsure of how to start with this one. I have thought to reducing the problem to Atm. Another thought I have had is to convert M1 to a PDA and use the ...
1 vote
1 answer
71 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 ...
0 votes
1 answer
969 views

Show that an instance of PCP or MPCP has no solutions

I'm studying the Post Correspondence Problem (PCP) and understand the concept, although I have problems with proving how to show that an instance of a PCP or modified PCP has no solutions. For ...
1 vote
1 answer
42 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 vote
1 answer
37 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 ∈ {...
0 votes
1 answer
40 views

If $B \in RE$ then $A \in RE$ - Reduction

I know that if there is a Turing Reduction from $A$ to $B$, say $A \le_T B$, and $B \in R$ then $A \in R$. I also know that Turing Reduction is for Decision, and not Recognition. Is it possible to ...
1 vote
1 answer
116 views

Mapping reduction properties exercise

I am having trouble understanding how to conclude if the statements are true or false, I would really appreciate your help. We know about three languages, A, B and C. There exists a mapping reduction ...
2 votes
1 answer
60 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 ...
1 vote
1 answer
64 views

$L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$

About the language $L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$ I want to determine if it is in RE / coRE or neither. I think that I found a mapping reduction from $\overline{A_{TM}}$ to $L$, ...
1 vote
1 answer
67 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 ...
1 vote
1 answer
1k views

Prove that clique cover is NP Complete

I want to use Vertex Cover as a known $NP$-complete Problem for the reduction. The claim is that if a have a vertex cover in graph $G$ with size $\le k$, I will have a clique cover in $G^\prime$ ...
4 votes
1 answer
84 views

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

I have a problem $\mathsf{A}$ and I would like to analyze its (parameterized) computational complexity. I found a parameterized reduction from the complement of the independent set ($\mathsf{coIS}$) ...
1 vote
0 answers
19 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 ...
6 votes
0 answers
87 views

Is it possible to reduce functional equations to SAT?

The problem of finding a solution for functional equations can be defined as: Let $A_0, A_1, A_2, \dots, A_n, B_0, B_1, B_2, \dots, B_n, X$ be terms of the $\lambda$-calculus, where all terms are ...
2 votes
2 answers
116 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 ...
1 vote
1 answer
111 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 ...
1 vote
0 answers
31 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 ...
4 votes
2 answers
121 views

Proving that DCONN is NL-Complete

I am having trouble with some homework regarding proving that DCONN is NL-Complete. As part of the exercise, the fact that RCH is NL-Complete can be assumed. Problem definitions: RCH: Given a ...
2 votes
1 answer
63 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 ...
1 vote
1 answer
182 views

Show problem is NP-hard

I'm preparing for my exam and I got stuck on the following problem: The gardening problem: We have access to a set of different types of seeds and a number of plant pots.For each plant pot, there is ...
0 votes
1 answer
94 views

Possible reduction from SUBSET-SUM

Given is a multiset $S$, a finite set $T = \{t_1, t_2, t_3\}$, and an integer $k \in \mathbb{N}$. Let $v(t_j)$ be a set of values $\in \mathbb{R^+}$ of length $|T|$ that can be assigned to $s_i$, and $...
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 ...
1 vote
2 answers
86 views

Reducing euclidean TSP of smaller size to euclidean TSP of bigger size

Assume I have a euclidean TSP solver that is optimal, but it can only solve inputs with exactly $N$ vertices. Let's call it the N-solver. Now, I have an input with $K$ vertices in the 2D plane, where $...
0 votes
1 answer
45 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 $\...
1 vote
1 answer
139 views

Covering maximal number of sets using fixed number of elements

I've encountered some problem which seems general enough to have already been solved. There is a set of objects $O=\{o_1, o_2,\dots,o_k\}$ and a family of sets $A_1,A_2,\dots,A_t \subseteq O$. For ...
2 votes
1 answer
546 views

Invertability of Karp reductions

Karp reducibility between NP-complete problems $A$ and $B$ is defined as a polynomial-time computable function $f$ such that $a \in A$ if and only if $f(a) \in B$. I am interested in polynomial-time ...
0 votes
1 answer
103 views

On FPTAS and many one parsimonious reductions

We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction. If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have? If $\Pi_2$ has an ...
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 (...
0 votes
1 answer
54 views

Reductions to perfect matching

Can we reduce any well-known problems to deciding whether a (possibly non-bipartite) graph $G$ has a perfect matching? I'm particularly interested in finding a reduction from deciding whether a ...
0 votes
1 answer
48 views

Reduction from a language with unknown decidability to HALT

We were taught to use reductions in order to show that a given L is undecidable. My question is, given some definition of a new L, is there a way to find a reduction $$ L\leq_mHALT $$ So that I can ...

1
2 3 4 5
26