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
1
vote
1answer
47 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
0answers
45 views

Deciding whether $f(x) = f(y)$ is beyond RE and coRE

I would like to prove that the following subset is outside both RE and coRE: $$A = \{ (p, (d_1, d_2,\dots, d_k)) \mid \text{for each } 1 \le i,j \le k, \; [p]d_i = [p]d_j \}, $$ where $p$ is a ...
1
vote
1answer
24 views

Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?

NL-Complete languages are defined by Log-space reduction, while PSPACE complete languages are defined by poly-time many-to-one reduction. According to these posts : Why not polynomial-space ...
2
votes
0answers
21 views

Concurrent Element-wise Reduction Algorithm (multi-threaded) (C++)

I'd like to implement a high-performance implementation of a multi-threaded reduction, element-wise, on x86 CPUs. Without loss of generality, assume the reduction operation is a sum of integers (so, ...
1
vote
1answer
76 views

Is Finding A Hitting Set of Size n/2 NP-Hard?

In Hitting Set problem we are given a collection E of subsets of V and we want to find smallest subset H of V which intersects (hits) every set in E. In decision version of the problem, we are asked ...
1
vote
1answer
70 views

Concrete example of Vertex Cover to Subset Sum reduction

In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem, mostly to prove Subset Sum is NP-Complete. I also see a reduction in the line ...
0
votes
1answer
30 views

I want to know where there is the flaw in my argument

I came across following problem to finding whether the following language is decidable or semi-decidable or not even a semi-decidable. $L: \{\langle M\rangle: M\space is\space a\space TM\space and\...
2
votes
2answers
110 views

How to prove NP-hardness from scratch?

I am working on a problem of whose complexity is unknown. By the nature of the problem, I cannot use long edges as I please, so 3SAT and variants are almost impossible to use. Finally, I have decided ...
0
votes
0answers
31 views
1
vote
0answers
103 views

Proof by reduction and Turing machines [closed]

This is a practice question I have, but I can't wrap my head around it. ............. Let L = {M | M is a TM that halts with exactly two words on its tape in the form Bw1Bw2B}. B = Blank Position the ...
2
votes
1answer
31 views

Can't find a mistake in reduction from RE language to a non-RE language

In the book Introduction to Automata Theory there is a question 9.3.4 that asks if a question "whether a language L(M) is infinite" is RE or non-RE? I've seen the answer, that its non-RE, however I ...
0
votes
1answer
45 views

Variant of TSP: allow each vertex to be visited at most twice

We are given a finite set $V$ and a set of distance $d : V\times V \rightarrow R\ge 0$ and we wish to compute a tour. Suppose we allow each vertex to be visited at most twice in the tour. How can we ...
1
vote
2answers
119 views

Is finding a minimal set of seed variables for a complete deduction of a system of equations NP-complete?

Suppose we have a set of variables $V$. We also have a set of equations $E$, which are sets of at least two variables. We don't know anything about these equations, except if we know all but one of ...
2
votes
1answer
429 views

Halting problem in EXP-complete

I have some troubles understanding why the halting problem is in EXP. In Wikipedia the following is written: It is in EXPTIME because a trivial simulation requires O(k) time, and the input k is ...
0
votes
1answer
49 views

A doubt on converting NOT gate to CNF formula

For a NOT gate if $x_1$ is input and $x_2$ is the corresponding output, I see the equivalent CNF (conjunctive normal form) is $(x_1 \lor x_2) \land (\overline x_1 \lor \overline x_2)$. My ...
1
vote
1answer
25 views

Differences between ALLTM and INF

The definitions of ALLTM and INF are as follows: $$\mathrm{ALLTM} = \{ \langle M \rangle \mid \text{ TM $M$ such that $L(M) = \Sigma^*$} \}. $$ $$\mathrm{INF} = \{ \langle M \rangle \mid \text{...
0
votes
1answer
57 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
3answers
83 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
39 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
28 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
56 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
5
votes
1answer
54 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
46 views

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

Let f: N → N be a function where ...
2
votes
0answers
69 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
39 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
62 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
35 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
60 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
55 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
38 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
133 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
29 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
117 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
56 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
16 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
40 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
27 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
85 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
36 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
30 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
33 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
51 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
52 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
26 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
51 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
94 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
23 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 ...