Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

2
votes
1answer
22 views

Decidability of equivalence of two context free grammars

I got a question regarding the decidability of equivalence of two context free grammars: Construct a Turing machine that decides whether $L(G) = L(H)$, where $G$ and $H$ are two context free ...
0
votes
0answers
18 views

Dimensionality Reduction to Find Abstract Concepts

I have a list of say 1000 topics and each are related to computer programming field such as if/else topic, while loop , for loop, integers, strings ect. I want to create a concept map for them which ...
2
votes
1answer
38 views

How to reduce a problem?

I am a bit confused on how to reduce a problem. I'll give an example: Let's say there is a problem called HALTEMPTY and we know it is undecidable. $HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ ...
1
vote
1answer
31 views

Prove if a property of a Turing Machine is decidable or not, how can I do it?

I cannot understand how to prove if a certain property of a Turing Machine M is decidable or not. For example, if a have this: (1.1) "M always halts within 100 steps" or this (1.2) "M recognizes ...
0
votes
1answer
32 views

On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem

in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it. Besides, it's easy to ...
0
votes
1answer
52 views

Existence of polynomial time reduction from P to R?

Why the next idea doesn't work: If L_2 in R and L_1 in P and the languages are not trivial, then there is a polynomial-time reduction from L_1 to L_2 I know ...
1
vote
2answers
47 views

How to define (logically) the complement language?

I found it a little bit difficult and confusing to define the complement language in specific cases. For example, take the next language: $$L = \left\{\langle M, w\rangle \;\middle|\; \begin{array}{...
1
vote
1answer
22 views

Is Rectilinear Steiner Tree still NP-complete when points have integral coordinates?

Garey proved that the Rectilinear Steiner Tree problem is (strongly) NP-hard. I wonder if it is still true when we retrict the points to have integral coordinates and lie on a square of side lenght n^...
0
votes
1answer
40 views

Alternate reduction from 3SAT to 4SAT?

It seems that the standard reduction method you see online from 3SAT to 4SAT is that we let $\phi = (a \lor b \lor c)$ be a 3SAT clause, and so there is an assignment that satisfies $\phi$ iff $\phi' =...
0
votes
0answers
30 views

Worked example of reduction from ILP to SAT

Can someone please show me a worked example of a polynomial time reduction of Integer Linear Programming to 3-SAT (in CNF)? Take a system of inequalities in the form: $$\mathbf{Ax} \leq \mathbf{b}$...
3
votes
2answers
33 views

Question about mapping reducibility

I am working on an assignment where one of the sub questions is: Let $A$ and $B$ be languages. Suppose $A$ is context free and $A ≤_m B$, which means that there is a computable function $f\colon \...
1
vote
1answer
17 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
57 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{ ...
1
vote
3answers
20 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
12 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:...
1
vote
1answer
26 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'\...
0
votes
0answers
31 views

String subsequence programming puzzle

I have a topcoder-like problem that I'm having trouble with: We are given three strings A, B and C. What is the length of the longest common subsequence of A and B, which has C as a substring? ...
1
vote
1answer
54 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. ...
2
votes
2answers
112 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
49 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 ...
4
votes
1answer
71 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
161 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
57 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
22 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
46 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
31 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
55 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
48 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
60 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
27 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
171 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
43 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
50 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
22 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
0answers
29 views

Is my logic correct and is this a new reduction and algorithm from 3 SAT to clique?

Is my logic correct? If so, is this a new reduction and algorithm from 3 SAT to clique? I could only find one SAT to clique reduction; it wasn't this. Definitions: A clause group of a SAT instance ...
0
votes
2answers
70 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
18 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
0answers
47 views

Turing Reduction vs Karp Reduction

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

Prove np-hardness of dividing items from the lists

I have a problem: There is finished number of lists of items. The same item can be on many lists. I would like to color items (there are 3 available colors) that on every list there are items in at ...
0
votes
0answers
23 views

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

I have a (probably) very easy question that I simply cannot wrap my head around. Basically I have to prove that $H\varepsilon = \{<M> \mid M \text{ halts on input }\varepsilon\}$ reduces to $H$ (...
2
votes
2answers
34 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
41 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$?...
4
votes
2answers
92 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
31 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
42 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
40 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
25 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!
0
votes
0answers
68 views

Gap-preserving reduction between $2lin_p$ and $3lin_p$

For a prime $p$, $\max-2lin_p$ is the problem of satisfying as many equations as possible from a system of linear equations modulo $p$, where every equation contains 2 variables. (Every equation is of ...
0
votes
0answers
42 views

Understanding reductions to 3SAT

EDIT: Upon further research I stumbled across a pdf from Yale which basically answered my questions. If wanted, I will post a follow-up answer later. As we are learning reductions to np problems at ...
-1
votes
1answer
43 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 ...