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
40
votes
4answers
13k views

What are common techniques for reducing problems to each other?

In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as ...
29
votes
2answers
8k views

How do I construct reductions between problems to prove a problem is NP-complete?

I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How ...
21
votes
2answers
2k views

Reduce the following problem to SAT

Here is the problem. Given $k, n, T_1, \ldots, T_m$, where each $T_i \subseteq \{1, \ldots, n\}$. Is there a subset $S \subseteq \{1, \ldots, n\}$ with size at most $k$ such that $S \cap T_i \neq \...
22
votes
3answers
2k views

Converting (math) problems to SAT instances

What I want to do is turn a math problem I have into a boolean satisfiability problem (SAT) and then solve it using a SAT Solver. I wonder if someone knows a manual, guide or anything that will help ...
19
votes
2answers
3k views

Can one show NP-hardness by Turing reductions?

In the paper Complexity of the Frobenius Problem by Ramírez-Alfonsín, a problem was proved to be NP-complete using Turing reductions. Is that possible? How exactly? I thought this was only possible by ...
4
votes
1answer
2k views

Does two languages being in P imply reduction to each other?

Given two languages $L_1$ and $L_2$ that are in $\mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how? I noticed that if $L_1$ is the ...
15
votes
3answers
5k views

If P = NP, why wouldn't $\emptyset$ and $\Sigma^*$ be NP-complete?

Apparently, if ${\sf P}={\sf NP}$, all languages in ${\sf P}$ except for $\emptyset$ and $\Sigma^*$ would be ${\sf NP}$-complete. Why these two languages in particular? Can't we reduce any other ...
25
votes
3answers
5k views

Teaching NP-completeness - Turing reductions vs Karp reductions

I'm interested in the question of how best to teach NP-completeness to computer science majors. In particular, should we teach it using Karp reductions or using Turing reductions? I feel that the ...
21
votes
5answers
37k views

How can I reduce Subset Sum to Partition?

Maybe this is quite simple but I have some trouble to get this reduction. I want to reduce Subset Sum to Partition but at this time I don't see the relation! Is it possible to reduce this problem ...
3
votes
1answer
1k views

Show that Halting problem $(\mathsf{HP\text{}})$ is $\mathsf{NP\text{-}Hard}$

Let me define first Halting problem $(\mathsf{HP\text{}})$. Given : $(M , x)$, $M$ is a turing machine and $x$ is a input binary string to turing machine $M$. Decide : Does $M$ halt on string $x$?...
11
votes
1answer
733 views

Reductions among Undecidable Problems

Im sorry if this question has some trivial answer which I am missing. Whenever I study some problem which has been proven undecidable, I observe that the proof relies on a reduction to another problem ...
2
votes
1answer
1k views

Reduction between $\Sigma^*$ and $\emptyset$

Throughout the subject of reductions, I was wondering: If we take $L_1 = \Sigma^* $ and $L_2 = \emptyset$, is $L_1 \leq L_2$? is $L_2 \leq L_1$? What I mean is, Is there some sort of reduction ...
15
votes
2answers
3k views

Types of reductions and associated definitions of hardness

Let A be reducible to B, i.e., $A \leq B$. Hence, the Turing machine accepting $A$ has access to an oracle for $B$. Let the Turing machine accepting $A$ be $M_{A}$ and the oracle for $B$ be $O_{B}$. ...
12
votes
2answers
2k views

Is Karp Reduction identical to Levin Reduction

Definition: Karp Reduction A language $A$ is Karp reducible to a language $B$ if there is a polynomial-time computable function $f:\{0,1\}^*\rightarrow\{0,1\}^*$ such that for every $x$, $x\in A$ if ...
18
votes
2answers
1k views

A polynomial reduction from any NP-complete problem to bounded PCP

Text books everywhere assume that the Bounded Post Correspondence Problem is NP-complete (no more than $N$ indexes allowed with repetitions). However, nowhere is one shown a simple (as in, something ...
4
votes
1answer
7k views

Is the language of Turing Machines that halt on every input recognizable?

I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is ...
17
votes
2answers
3k views

Reducing the integer factorization problem to an NP-Complete problem

I'm struggling to understand the relationship between NP-Intermediate and NP-Complete. I know that if P != NP based on Ladner's Theorem there exists a class of languages in NP but not in P or in NP-...
9
votes
2answers
3k views

Infinite alphabet Turing Machine

Is a Turing Machine that is allowed to read and write symbols from an infinite alphabet more powerful than a regular TM (that is the only difference, the machine still has a finite number of states)? ...
3
votes
0answers
432 views

Hardness of counting solutions to NP-Complete problems, assuming a type of reduction

The $\text{NP-Complete}$ class of problems is defined w.r.t Karp Reductions, which are polytime many-one reductions. However, they need not necessarily preserve the number of solutions. A more ...
4
votes
2answers
2k views

Reduce Vertex Cover with size k to Vertex Cover with size n/2

Disclaimer: This is a homework question. I would like to reduce vertex cover problem to the following problem: $$L = \{G \mid G\text{ has a vertex cover of size } |V(G)|/2\}\,.$$ I have divided the ...
1
vote
2answers
171 views

If $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$

How to prove if $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$ ? it means every recursive set is mapping reducible to set $B\neq \aleph$. I really have no idea ...
10
votes
2answers
1k views

Can we construct a Karp reduction from a Cook reduction between NP problems?

We have had several questions about the relation of Cook and Karp reductions. It's clear that Cook reductions (polynomial-time Turing reductions) do not define the same notion of NP-completeness as ...
4
votes
1answer
323 views

Undecidability of REGULAR_TM (Detail within Proof)

I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book. The example shows how $REGULAR_{TM}$, defined as the ...
4
votes
1answer
1k views

$\mathsf{co\text{-}NP}$ and Cook reductions

Can someone help me understand the steps in this argument? There is a decision problem that is in $\mathsf{co\text{-}NP}$ (under standard Karp reductions) and is $\mathsf{NP}$-hard with respect to ...
4
votes
1answer
9k views

Proving NP Completeness of a subset-sum problem - how?

So I'm trying to understand P/NPC problems. The one I'm trying to tackle now is subset sum (we have a collection of integers $S$ and a $k$ param: is there a subset of $S$ that sum of all it's elements ...
3
votes
1answer
2k views

Reducing from a Turing machine that recognizes is regular to the halting problem

I'm trying to understand reduction, this is from my textbook and is not a homework problem or even any exercise, just trying to understand an example they present. This is the reduction they give: ...
3
votes
1answer
14k views

How to prove NP-hardness of a longest-path problem?

I have this question: ...
3
votes
1answer
237 views

Machines whose languages are their own encoding

Is the language $S = \{\langle M \rangle \mid M \text{ is a Turing Machine and } L(M) = \{\langle M \rangle\}\,\}$ decidable, recognizable and/or co-recognizable? I tried diagonalization but can only ...
3
votes
1answer
676 views

Space(n) not closed under Karp reductions - what about NTime(n)?

In the book on complexity by Arora and Barak, there is an exercise to show $Space(n)\neq NP$, the proof of which goes by showing that $NP$ is closed under Karp reductions, while $Space(n)$ isn't. To ...
2
votes
1answer
2k views

What is a “reduction”, really?

I am studying computational theory with Sipser's textbook. I can't quite understand the definition of "reduction". For example, "this problem can be reduced to ATM ..." What exactly does "to reduce" ...
14
votes
1answer
515 views

Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$

We know that $st\text{-}non\text{-}connectivity$ is in $\mathsf{NL}$ by Immerman–Szelepcsényi theorem theorem and since $st\text{-}connectivity$ is $\mathsf{NL\text{-}hard}$ therefore $st\text{-}non\...
6
votes
1answer
1k views

Is it decidable whether a Turing machine modifies the tape, on a particular input?

Is $L=\{\langle M,w \rangle|M\text{ does not modify the tape on input w}\}$ decidable? We could tell if a TM does not modify the tape on any input by checking if there are no transitions in $M$ that ...
5
votes
1answer
840 views

Transforming SAT to Quadratic Programming in polynomial time

I would like to show that Quadratic Programming is NP-hard. I am currently reading a couple of papers which state that QP is NP-Hard and prove it by transforming SAT to QP, however I am finding the ...
5
votes
1answer
3k views

Optimization problem vs decision problem - reduction

Assume we have an optimization problem with function $f$ to maximize. Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
2
votes
2answers
2k views

Reducing optimization problem to decision problem

I'm trying to reduce an optimization problem to a decision problem, more specifically, consider the Max-Cut problem in its decision version: Given $(G=(V,E),k)$ as input, where $G$ is an undirected ...
2
votes
2answers
2k views

CNF Generator for Factoring Problems

I've been reading these: Fast Reduction from RSA to SAT CNF Generator for Factoring Problems (Also have C code implementation) I don't understand how the reduction from FACT to $3\text{-SAT}$ works. ...
1
vote
1answer
863 views

Reduction from PARTITION to 3PARTITION

I'm considering the problem (a variant of 3-PARTITION, see here) with description Instance: Set of positive integers $A={w_{1},...,w_{n}}$ with $S(A)=\sum\limits_{i=1}^{n}w_{i} = 3m$. ...
1
vote
1answer
2k views

Reduction from P to NP

Conceptually, I know that reducing a problem $Y$ that's NP-complete to a problem $X$ implies that $X$ is at least as hard as $Y$, implying $X$ is also NP-complete. So if any NPC problem, say $Z$, can ...
0
votes
1answer
307 views

Implications of Halting Problem being unsolvable?

I came across a confusing situation when reducing the Halting Problem (HP) to the Blank Tape Accepting Problem (BP). We know that since HP can be reduced to BP, BP is decidable $\implies$ HP is ...
7
votes
2answers
654 views

Complete Problems for $DSPACE(\log(n)^k)$

We know that the $polyL$-hierarchy doesn't have complete problems, as it would conflict with the space hierarchy theorem. But: Are there complete problems for each level of this hierarchy? To be ...
3
votes
1answer
419 views

How exactly does a Max 2 Sat reduce to a 3 Sat?

I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after <...
1
vote
2answers
447 views

Is it decidable that a context free language contains a given regular language?

I've been asked to solve this problem, but I'm completely stuck now. Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable? I know I've to find a ...
1
vote
2answers
1k views

P=NP, isn't it?

Cook and Levin showed in 1971 how deterministically in polynomial time from every non deterministic Turing machine M, that halts in polynomial number of moves/steps, and string w to create the boolean ...
1
vote
1answer
415 views

Reducing the infinite language problem to halting problem

Let: $INF = \{ w \in \Sigma^* | \quad |L(M_w)| = \infty \} $. It is easy to show with Rices theorem that $INF$ is not decidable. ($INF$ is non-trivial because of $\emptyset$ and $\Sigma^*$). How ...
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 ...
0
votes
0answers
269 views

Hamiltonian path in dynamic graph

Given an undirected Graph. I want to find a hamiltonian path with no restriction to starting or ending vertices. I know there are some smart algorithms for solving that. Now let's make things ...
20
votes
2answers
3k views

Subset Sum: reduce special to general case

Wikipedia states the subset sum problem as finding a subset of a given multiset of integers, whose sum is zero. Further it states that it is equivalent to finding a subset with sum $s$ for any given $...
9
votes
2answers
920 views

For any language $A$, there is $B$ such that $A \le _T B$ but $B \nleq _T A$

I am trying to come up with a proof for the following: For any language $A$, there exists a language $B$ such that $A \le_{\mathrm{T}} B$ but B $\nleq_{\mathrm{T}} A$. I was thinking of letting $B$...
18
votes
1answer
1k views

Could min cut be easier than network flow?

Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
20
votes
3answers
10k views

HALF CLIQUE - NP Complete Problem

Let me start off by noting this is a homework problem, please provide only advice and related observations, NO DIRECT ANSWERS please. With that said, here is the problem I am looking at: Let HALF-...