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
1answer
29 views

Is every Turing complete set for EXPSPACE autoreducible?

I'm reading about autoreducibility, which is the following notion: A set $L$ is autoreducible if there is a polynomial-time oracle Turing machine $M$ that accepts $L$ using $L$ as an oracle, ...
0
votes
1answer
31 views

How Reduction works in proving NP-Hard?

A problem $X$ is $NP$-Hard if for all $Y \in NP$, $Y \leq_P X$. Further, if a problem $Z$ is $NP$-Complete, and $Z \leq_P X$, then I can prove (rather mechanically) that $X$ is $NP$-Hard. I also ...
1
vote
1answer
34 views

Why is $ZPP \geq BPP$ not true?

This seems like a silly question, but I couldn't find a conclusive answer for it. As far as I know, ZPP contains algorithms which run in polynomial time and either return a known-correct answer or ...
1
vote
1answer
25 views

Prove that there is no computability reduction HP $\le$ $\Sigma$*

I tried to prove in negative way that there is computability reduction HP $\le$ $\Sigma$* and accept contradiction because of HP $\in$ RE and $\Sigma$* $\in$ R but it feels that is not strong ...
1
vote
2answers
42 views

Reduce subset sum to 3SAT

How to do it? I'm not asking the solution for the proof of why subset sum is NPC, but rather the opposite reduction
4
votes
1answer
38 views

NP-hardness even with perturbations

Consider the following problem, which can be called "2-SET-PARTITION": Given two sets of positive numbers, $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$, where $\sum_{i\in[n]}a_i = \sum_{i\in[n]}b_i = 2 S$,...
4
votes
1answer
33 views

Normal colorings of cubic graphs to SAT

This problem is related to ”Normal coloring of cubic graphs (part 1) - a previous post. We repeat the definitions, slightly modified so as to get to the point (we define normal edge 5 colorability, ...
0
votes
1answer
45 views

Is function `number of TM which terminates on an empty word` computable?

Let f: N → N be a function where ...
2
votes
0answers
68 views

Proving NP-completeness of an extension in List Coloring Problem

In the List Coloring Problem (LCP), one is given an undirected graph $G(V,E)$, each vertex $v \in V$ is given a list of permissible colors $L(v) \subseteq \{1,2,\dots,k\}$, we want to find a coloring $...
1
vote
1answer
33 views

Reduction to proof undecidability of the problem: machine M and N accept infinitely many words

I am struggling with the following problem: Decide whether this problem is decidable or not: For two given Turing Machines M and N, there exists infinitely many words accepted by both machine M and ...
2
votes
1answer
56 views

How to prove the language of Turing machines that run at most $4|x|^2$ steps is not recursive?

I am trying to prove that the language $$ L=\{M\mid M\text{ is a TM and for all }x\in \Sigma^*\text{ with }|x|>2, M\text{ on }x\text{ runs at most }4|x|^2\text{ steps}\} $$ belongs to Co-RE but ...
0
votes
0answers
24 views

Proving 3-Hitting Set is NP complete

Consider the following desicion problem: 3-Hitting Set - This problem is indentical to the classic Hitting Set problem with the following constraint: Each set has to be exactly 3 items long. Similarly ...
1
vote
1answer
47 views

How to prove $L \notin \texttt{DSPACE}(f)$

I want to prove that a language $L$ is not in $\texttt{DSPACE}(f(n))$, the class of languages that a deterministic Turing machine can decide with fixed tape length of $f(n)$ (wiki). That is, I want to ...
3
votes
2answers
33 views

Solving the min edge cover using the maximum matching algorithm

To solve an instance of an edge cover, we can use the maximum matching algorithm. Edge Cover: an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least ...
1
vote
1answer
29 views

Reducing 3 SAT to 3 SET PACKING

I'm trying to prove NP-hardness of 3 SET PACKING, which is a following problem: given a family of sets where each set contains 3 elements, decide whether the family contains k sets that are pairwise ...
0
votes
2answers
83 views

Reducing Graph Reachability to SAT (CNF)

So I came across this problem in my textbook. I was wondering how to develop a reduction from the Graph Reachability problem to SAT (CNF) problem. (i.e. formula is satisfiable iff there exists a path ...
1
vote
1answer
30 views

Is $\bigcup_{c \ge 1} \mathsf{DTime}(2^{cn})$ closed under polynomial reduction?

It's well known $EXP$ is closed under polynomial reduction. It means $\bigcup_{c \ge 1} \mathsf{DTime}(2^{c^{n}})$ is closed under polynomial reduction. But what about $\bigcup_{c \ge 1} \mathsf{...
2
votes
1answer
25 views

Log-Space Reduction $USTCON\le_L CO-2Col$

I want to show that $USTCON\le_L CO-2Col$ (Log-Space reduction) $USTCON$ The $s-t$ connectivity problem for undirected graphs is called $USTCON$. Input: An undirected graph $G=(V,E)$, $s,t \in V$. ...
3
votes
0answers
75 views

Minimum clique cover

How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time? Having an undirected graph, I am trying to partition all its ...
0
votes
1answer
50 views

pseudo-polynomial reduction from 3-Partition to Partition

A problem $\Pi'$ is pseudo-polynomially reducible to the problem $\Pi$ ($\Pi' \leq_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in pseudo-polynomially ...
1
vote
0answers
14 views

Example of a Karp reduction between problems in NP that is not a Levin reduction?

What is an example of a Karp reduction $f$ between two problems $A, B$ in $\textbf{NP}$ such that $f$ does not provide a way to transform certificates of one problem into certificates of the other? In ...
2
votes
1answer
26 views

Showing Maximum Independent Set is $NP-hard$

I've read about Maximum Independent Set problem being both $NP-hard$ and $CoNP-hard$. I know this can be shown using reduction from the corresponding Max-Clique problem, But I'm wondering - Is that ...
2
votes
1answer
24 views

NL-Hardness of Target

When revising for an upcoming exam in complexity theory, I came across this problem on the final part of a question, which I was unable to solve: $ TARGET = \{<G, t> : t\ is\ reachable\ from\ ...
2
votes
1answer
81 views

Can these two languages be reduced to one another?

Given: $L_1=\left\{ \left\langle M\right\rangle :L\left(M\right)\ni w_{0}\right\}$ $L_2=\left\{ \left\langle M\right\rangle :L\left(M\right)=\left\{ w_{0}\right\} \right\}$ I believe I've managed ...
2
votes
1answer
32 views

Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?

We say that two languages $L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $f:\Sigma^*\to\Sigma^* $ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^*$ ...
0
votes
0answers
23 views

Dominating Set Gap Problem Reduction

In the reduction from Vertex Cover problem to Dominating Set a new vertex is added for each edge in the original graph. Specifically, Given graph $G=(V,E)$ where $|V|=n$ with $VC$ with size $k$ we ...
1
vote
1answer
26 views

Reduction from NP-complete problem to unknown complexity problem and vice-versa

Suppose I have two problems: $B$, which is NP-complete, and $A$, of unknown complexity. Question: If I show that $B \le A$ I can state that $A$ is also NP-complete because the two required ...
2
votes
1answer
44 views

How to reduce EQU to UNI?

Let $$\texttt{EQU}=\{u\#v \mid T(M_u)=T(M_v)\} \\ \texttt{UNI}=\{w \mid T(M_w)= \Sigma^*\}$$ How can you prove $\texttt{EQU} \leq \texttt{UNI}$? The idea I have so far is, to simulate the TM that ...
3
votes
1answer
47 views

How to reduce $\{w \mid |T(M_w)| \geq 42\}$ to the halting problem?

For a string $w$, $M_w$ denotes the Turing machine whose encoding is $w$. I want to reduce the language $L=\{w \mid |T(M_w)| \geq 42\}$ to $H_0 = \{w \mid M_w \text{ halts on } \epsilon\}$, but I ...
2
votes
0answers
24 views

NP-completeness of Induced disjoint paths between a set of sources and a set of sinks

In a given undirected graph $G(V,E)$, a set of $k$ paths is said to be induced if: They are vertex-disjoint. Each one is itself an induced path. No edge connects two vertices of two different paths. ...
-1
votes
1answer
29 views

If a problem C is NP hard and there is an existing reduction from/to A,B,D, are they NP hard as well?

Lets say there is an reduction in polynomial time from problem A to B, from problem B to C and from problem C to D. Now lets say C is NP hard. Does this mean A,B,D are NP hard as well?
2
votes
2answers
50 views

Turing machine reduction task

I am having trouble solving the following task: Given is the language $$D=\{ \langle M, w \rangle \mid \text{$M$ is a Turing machine and $M$ enters all states on input $w$}\}$$ Prove that $D$ ...
1
vote
3answers
55 views

How to solve the optimization of bin packing using the decision version

Let us say the optimization version of the bin packing problem asks you to give a packing using the fewest bins possible and the decision version asks if it is possible to pack the bins into $k$ bins. ...
0
votes
0answers
22 views

Two (oracle) turing machines producing the same language

I need to solve the question if two given oracle turing machines M$_{1}$ and M$_{2}$ have the same language, so T(M$_{1}$) = T(M$_{1}$). An oracle turing machine can use such an oracle for deciding ...
5
votes
1answer
79 views

Reduction from Exact Cover to Fixed Exact Cover

I am trying to reduce Exact Cover to Fixed Exact Cover to show that Fixed Exact Cover is NP-Hard. Exact Cover Input S = {x1, x2, ..., xn} (set) P = {P1, P2, ..., Pm} (subsets of S) Decision ...
1
vote
1answer
47 views

Parity Hamiltonian path problem

Wikipedia says that Hamiltonian path problem is NPC, but Parity Hamiltonian path problem (i.e., is there an odd amount of hamiltonian path) is P. Does a reduction from, e.g., SAT, to HPP, unavoidably ...
1
vote
1answer
35 views

Prove disprove an existence of mapping reduction between 2 sets

I am currently studying mapping reduction in computational theory and finding it hard to grasp the concept fully. For reference, consider the following given WHILE-Prog sets: A = { (p.d) | p doesn'...
0
votes
1answer
13 views

Is $L=\{\langle M\rangle\mid L(M)\subseteq HP\}\in coRE$?

My intuition is that $L\notin coRE$, but I haven't managed to prove that $HP \le L$, as previously I only saw reductions from $HP$ or from $\overline{HP}$ with $f$ such that $f((\langle M\rangle,x))=\...
1
vote
1answer
34 views

If a problem Q is NP complete, is another problem reducible to Q also NP complete?

Let's say $\mathcal{P}$ is a yes/no prolem with an existing reduction to the problem $\mathcal{Q}$ (with time complexity $\mathcal{O}(n^2)$). $\mathcal{Q}$ is NP complete. Does this mean that $\...
0
votes
1answer
35 views

If well-founded induction holds, then the relation $\to$ on a reduction system terminates

I am trying to understand a proof from "Term Rewriting and All That" by Baader and Nipkow. Well-founded induction (WFI) is the following statement: $\forall x \in A(\forall y \in A(x \stackrel{+}{\...
1
vote
1answer
38 views

Proving that the set of grammars generating L or L complement is undecidable

Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
5
votes
1answer
155 views

Prove that “Finishing the degree in three years” problem is NP-Complete

I was asked in an interview the following question: We'll define the "Finishing the degree in three years" problem in the following manner: Given a list of courses $C=\{c_1, c_2,\ldots, c_n\}$, ...
2
votes
3answers
74 views

If P = NP, does SAT, or any other NP-Complete poly-reduce to any language different from $\emptyset$ or $\Sigma^*$?

I looked at Sipser ("Introduction to the Theory of Computation"), Problem 7.17: Prove that if P = NP, then every language in P, except $\emptyset$ and $\Sigma^*$, is NP-Complete. The solution is ...
2
votes
1answer
96 views

Proving NP hardness in Puzzle with SAT reduction

Introduction I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The algorithm follows an infinite language based on ...
2
votes
1answer
100 views

Is maximum-leaves spanning tree np-complete?

How can we show that a maximum-leaves spanning tree is NP-complete? what other np-complete problem we can use as our reduction base? (maximum-leaves spanning tree: does G have a spanning tree with at ...
1
vote
1answer
208 views

for two languages in $NP$ does one of them karp reducible to another?

$\forall A, B \in NP \implies A<_m^{poly}B. \lor B<_m^{poly} A.$ I want to know is there any work around this theorem? or is it correct?
2
votes
1answer
84 views

Why is Graph Isomorphism downward self reducible?

To say that graph isomorphism is downward self reducible means the following: There is an algorithm which decided graph isomorhpism for two given graphs of n vertices in polynomial time by accessing ...
3
votes
1answer
350 views

reduction from 3-SAT to Subset Sum problem

How to reduce 3-SAT to subset sum problem?
0
votes
0answers
191 views

How can I reduce Subset Sum to Almost Subset Sum?

Maybe this is quite simple, but I am having some trouble how to do this reduction. I want to reduce Subset Sum to Almost Subset Sum. Subset Sum: given a set of positive integers $A=\{a_1,a_2, \dots,...
0
votes
2answers
50 views

Assume we have an algorithm HC for HAMILTONIAN CIRCUIT. How is it possible to convert the HC algorithm to an algorithm HP for HAMILTONIAN PATH?

My understanding is that I have to use the algorithm for Hamiltonian Circuit to help solve the Hamiltonian Path problem. My understanding is that we have to perform a reduction from Hamiltonian Path-...