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
20 views

Weakest reduction for 3-$\mathrm{SAT}$

Having read all these posts Constant-depth threshold circuit for $\mathrm{PP}$ Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}_6}^0=\mathrm{NP}$ I wonder about ...
3
votes
1answer
116 views

$TSAT$ is $NP$-complete

In "Computational Complexity" by Arora and Barak they state that the following is $NP$-complete: $\{ \langle \alpha, x, 1^n , 1^t \rangle : \exists u \in \{0,1\}^n \text{ s.t. } M_{\alpha} \text{ ...
0
votes
3answers
42 views

Collection of meta-reductions in theory of $\mathrm{NP}$-completeness

I want to start a wiki post about meta-result of meta-reductions in the theory of $\mathrm{NP}$-completeness. This can be regarded as a reference request post. Any links are appreciated. At least, ...
0
votes
1answer
103 views

Is this reduction from 3D-MATCHING to PATH SELECTION invalid?

I'm a bit confused about some proof that PATH-SELECTION-PROBLEM is NP-complete (Problem 9, chapter 8 in "Algorithm Design" by Tardos and Kleinberg) that I found in some solution manual here: https:...
0
votes
1answer
38 views

Cook completeness of a variant of Vertex Cover

Is this variant of Vertex Cover Cook-complete for $\mathrm{NP}$? Input: An undirected graph $G(V, E)$ together with a vertex cover $C\subseteq V$ Output: YES if there exists a vertex cover $C'\...
1
vote
1answer
62 views

Looking for a problem provably not in P

My basic position is that everything is in P. Then comes the time hierachy theorem and EXP. That's easy: simulate and then diagonalize. After that comes EXP-completeness; that's difficult to swallow. ...
3
votes
2answers
274 views

Is this problem NP-hard? Maximizing selected sets so that their union is less than k?

There is an NP-hard problem called Minimum k-Union where we are given a set system with $n$ sets and are asked to select $k$ sets in order to minimize the size of their union. I'm currently ...
2
votes
1answer
56 views

Understanding reductions for NP-completeness

Let's I have to make the following reduction: $$\text{CLIQUE}\le_p \text{VERTEX-COVER}$$ The technique of building the reduction is - Assume you can find a $\text{VERTEX-COVER}$ of size $k$, in ...
2
votes
1answer
95 views

Path in a vertex-weighted undirected graph

Is it an $NP$-hard problem? You're given an undirected graph $G(V,E)$ with vertex weight $w: V \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$. Does ...
3
votes
2answers
700 views

PCP undecidability

There is a popular proof for the undecidability of the PCP (Post correspondence problem), which is outlined here: https://en.wikipedia.org/wiki/Post_correspondence_problem I'll assume whoever will ...
1
vote
2answers
230 views

Solve Hamilton Circuit with Hamilton Path

I want to show the reduction $HC \leq HP$. Let $G=(V,E)$ be my undirected graph. My idea is: For each edge $e=(u,v) \in E$ check whether $(V,E\backslash\{e\})$ has a Hamiltonian Path. If this is true ...
2
votes
1answer
61 views

If $L=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)=\Sigma^* \big\}$ is in $RE$ or $coRE$ or not in $RE\cup coRE$?

I tried to solve it as the following: $$\overline{L}=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)\neq\Sigma^* \big\}$$ I'll show that $\overline{L}\not\in RE$ by ...
0
votes
0answers
57 views

Finding reduction to prove that a language is NP-complete

I need to prove that the following problem is NP-complete: We have $n$ diplomats from $n$ countries and we need to seat them around a round table. We also get a list of diplomats who don't get along ...
1
vote
1answer
39 views

How to start solving this type of exercise: Determine if $L$ is in $RE\setminus coRE$ or $coRE\setminus RE$ or $R$ or not in $RE\cup coRE$?

I'm asking this, because in every exercise I check if I can relate it to one of the things I know, like:$A_{TM}$, $\overline{A_{TM}}$, ${HALT_{TM}}$,$\overline{HALT_{TM}}$, $E_{TM}$, $\overline{E_{...
1
vote
1answer
159 views

Is any sudoku solver an SAT solver?

I have recently created a sudoku solver using C#, which outputs the solution to a sudoku after a reasonable amount of time in many cases. I have used the basic sudoku SAT-reduction (i.e. x111 meaning ...
2
votes
2answers
176 views

Circuit satisfiability problem : SAT-C to SAT-2C

I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C. Prove that ...
2
votes
1answer
113 views

“Fuzzy” Chinese Remainder Theorem NP-hard?

I have some "fuzzy" congruences like these: \begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{0,3\},\\x&\equiv a_3 \mod 7 \...
1
vote
1answer
31 views

polynomial time reducibility - $L_{2} \notin \textbf{P}$ and $L_{1} \leq_{p} L_{2} \implies L_{1} \notin \textbf{P}$

If we have two languages $L_{1} \subseteq \Sigma^{\ast}_{1}$ and $L_{2} \subseteq \Sigma^{\ast}_{2}$ I proved that when $L_{2} \in \textbf{P}$ and $L_{1} \leq_{p} L_{2}$ then $L_{1} \in \textbf{P}$ ...
1
vote
2answers
601 views

What are known 3SAT to 2SAT reductions?

Is there a way to convert a 3SAT formula into a equisatisfiable 2SAT formula? Each method is of interest, even those that grow exponentially. (So if, for example, my 3SAT formula has 16 variables and ...
0
votes
1answer
45 views

A Language Belonges to PSPACE

Let $A,B$ be two languages, for which we know: $A \in PSPACE$ $A\le_LB$ Can we conclude from the above that $B \in PSPACE$ ? I think the answer is no, however I don't know how to ...
2
votes
1answer
55 views

Careful 5COLOR NP hardness

Given the following definition of Careful 5COLORING: A 5-coloring is careful if the colors assigned to adjacent vertices are not only distinct, but differ by more than 1(mod 5) how would a ...
0
votes
0answers
64 views

$2$-partition reduction for weighted completion time in scheduling

I've read about the reduction from $2$-partition for the problem of minimizing weighted completion time with release dates but I'm not very experienced in doing reductions so I want to verify that my ...
0
votes
2answers
87 views

Can we reduce an NP to an NP Problem?

Lets say Problem A,B are in NP. Can we reduce Problem A to B? Meaning A $≤_p$ B? or A $≤_t$ B Is there a difference in "hardness" of a Problem even in NP? Or must Problem B at least be NP-Complete?
0
votes
0answers
63 views

Karp Reduction L1 ≤p L2

Given: $L_1 = \{0^k1^k|k \in \mathbb{N}\}$ $L_2= \{1\}$ $L_1 \leq_p L_2$ There must be a function $$f:Σ^* \rightarrow Σ^*$$ such that $$w \in L_1 \iff f(w) ∈ L_2$$ Let's say a word in $L_1$ is ...
1
vote
1answer
291 views

Turing Reduction vs Karp Reduction [closed]

When do you use Turing- and when Karp Reduction? What are the advantages and disadvantages? I've read about Karp Reduction mainly used in the Context of reducing a Language: e.g. L1 $≤_p$ L2
2
votes
1answer
75 views

Prove np-hardness of dividing items from the lists

I have the following problem. Given a finite number of lists of items. The same item can appear in many lists. I would like to color items with 3 colors, such at least two colors appear in each list. ...
1
vote
1answer
131 views

Prove that $H$ reduces to $H\varepsilon$

I have to prove that $H_\varepsilon = \{<M> \mid M\ \text{halts on input }\varepsilon\}$ reduces to $H$ (the halting problem). I am very confused how to PROVE it, I mean it is clear that we can ...
2
votes
2answers
49 views

Is every reduction function $f \in O(n)$?

I have no detailed questions actually. My question is about a (maybe possible) generalization for reductions. We defined reduction as following (If I translate a term false please correct me.): $ ...
0
votes
1answer
181 views

Prove that Weighted Independent Set is NP Complete using Independent Set?

$k$-Weight Independent Set Input: A vertex weighted graph $G=(V,E,w)$ and an integer $k$. Question: Is the a set $V'\subset V$ such that $V'$ is an independent set and $\sum_{v\in V'} w(v) \geq k$?...
5
votes
2answers
185 views

What does “AC0 many-one reduction” mean?

What does $\mathsf{AC^0}$ many-one reduction mean? I know about polynomial time reductions, but I'm not familiar with $\mathsf{AC^0}$ reductions.
-1
votes
1answer
36 views

mapping reduction from $A_i=\{x|i \in W_x\}$ to $A_j=\{x|j \in W_x\}$

If $$ A_n = \{ x | n \in W_x\} \ where \ W_x \ is \ domain \ of \ M_x $$ how can I show that $$ \forall i,j \ \ \ A_i \le_M A_j $$
2
votes
1answer
143 views

Prove that the TM which would go over the leftmost position is not decidable

Let $M$ be a one-band TM and $w$ a word. We say that M tries to move the head over the left margin of the band if, while the head is in the leftmost position of $w$, the TM $M$ tries to move to the ...
1
vote
1answer
86 views

If A is reducible to B and B is reducible to A, and A is NPC, is B also NPC?

I was thinking about the max-clique problem and the k-independent set problem. You can show that k-independent set is reducible to max-clique easily and you can show that max-clique is reducible to k-...
0
votes
1answer
142 views

Do you have to do reduction both ways to prove a problem is NPC?

Also, what's the difference between transforming a problem into another problem and doing a reduction? They sound synonymous to me. Thank you!
-1
votes
1answer
50 views

Prove/Disprove: If $A _{\leq M} B$ and $B _{\leq M} A$ then $A=B$

Given $A, B$ languages over $\Sigma,$ Prove/Disprove: If $A _{\leq M} B$ and $B _{\leq M} A$ then $A=B$. I would like to disprove this claim, with the languages $H_{TM}$ and $H_\epsilon = \{\langle ...
0
votes
1answer
72 views

is it possible to have a mapping reduction between 2 NP complete languages?

so i have a good understanding about languages that belong to NP, P and NP complete, and how Polynomial reduction works between languages that belong to those areas. but i just can't figure out a ...
0
votes
0answers
26 views

Prove that a language is undecidable by reducing HALT to it [duplicate]

Let $L = \left\{ \langle \alpha, x\rangle \mathrel{}\middle|\mathrel{} \textrm{x is the only string accepted by}\mathrel{}M_\alpha \right\}$ and $HALT = \left\{ \langle \alpha, x\rangle \mathrel{}...
3
votes
1answer
226 views

A TSP to HamCycle Reduction

I'm referring to the decision version of both $TSP$ and $HamCycle$. The first is, given a graph $G=(V,E)$, a weight function $w:E\rightarrow \mathbb R^+$ and an integer $k$, is there a simple cycle ...
1
vote
2answers
33 views

If a decision problem $A \in \text{NP}$ and there exists reduction so that $A \leq_p B$, for decision problem B, what can be deduced about B?

I think that it implies that B can be solved by a non-deterministic polynomial time or worse Turing machine, but I realise that there is possibly some greater result that I'm missing. Thanks in ...
2
votes
2answers
209 views

Is it NP hard to decide whether there exists a subset of V of size at most $k$ hitting all maximal bicliques of G?

The following problem is from my algorithms class: Given a graph $G(V, E)$, a set $C \subseteq V$ is called a biclique iff $G[C]$ is a complete bipartite graph, where $G(C)$ is the subgraph ...
3
votes
1answer
117 views

Is it NP hard to partition a graph into 2 vertex sets with minimum degree of 2 and 3?

The following problem is from my algorithms class: Given a graph $G=(V, E)$, decide whether a partition of $V=(V_1, V_2)$ exists such that $\delta(G(V_1))\ge 2 $ and $\delta(G(V_2))\ge 3 $, where $...
0
votes
1answer
159 views

Reducing INDSET and MAXCUT to 3SAT

Given a graph and an integer $k$ is there an independent set larger than $k$ is INDSET problem and is there a cut larger that $k$ is the MAXCUT problem. Is there standard way to convert to 3SAT from ...
2
votes
1answer
67 views

Transitivity of quasi-reducibility

A set $A$ is quasi-reducible to $B$ ($A \leq_Q B$) if there is a recursive function $f$ such that $$x \in A \iff W_{f(x)} \subseteq B$$ Or equivalently $$ x \in \overline{A} \iff W_{f(x)} \cap \...
14
votes
5answers
4k views

How to prove the existence of a number which cannot be written by any algorithm?

I have the problem: Show that there exists a real number for which no program exists that runs infinitely long and writes that number's decimal digits. I suppose it can be solved by reducing ...
2
votes
2answers
276 views

Is it NP complete to decide whether a graph has $k$ disjoint triangles?

I'm trying to prove that $$k\text{-Matching}\le_p k\text{-Disjoint-Triangles}$$ but I was told that the $k\text{-Matching}$ (decide whether a graph has a matching of size $k$ ) can be solve in ...
0
votes
1answer
58 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
1answer
108 views

Maximize vertex cover weights with bounded edge weights in a connected subgraph

Similar questions were asked elsewhere, but no satisfying answers occurred yet. In a graph with weights for both vertices and edges, I want to find a subgraph, whose sum of internal edge weights is ...
-1
votes
1answer
76 views

Show that a problem belongs to NP

A logistics company has two trucks and has to deliver some packages to some addresses. The manager has to create a plan for every driver. Input Data: A set of V locations, an array d[v,u] for every ...
1
vote
1answer
63 views

Problem with the mapping reduction from $A_{TM}$ to $HALT_{TM}$

Sipser provided the following proof to prove the mapping reduction from $A_{TM}$ to $HALT_{TM}$, it in fact tried to build a mapping function: My problem is the way this proof works. The function ...
2
votes
1answer
33 views

Complexity Reduction Analysis

I am struggling to grasp fully grasp complexity reductions, I have this example that I am working through and can not fully comprehend how to determine the complexity of one algorithm given the ...