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].
1,246
questions
44
votes
4
answers
18k
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 ...
- 71.8k
37
votes
2
answers
17k
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 ...
- 371
31
votes
1
answer
7k
views
Sorting as a linear program
A surprising number of problems have fairly natural reductions to linear programming (LP). See Chapter 7 of [1] for examples such as network flows, bipartite matching, zero-sum games, shortest paths, ...
- 4,037
30
votes
1
answer
963
views
Graph problem known to be $NP$-complete only under Cook reduction
The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a ...
- 4,387
29
votes
5
answers
57k
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 ...
- 497
29
votes
3
answers
9k
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 ...
D.W.♦
- 152k
24
votes
2
answers
4k
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 \...
- 1,121
23
votes
3
answers
3k
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 ...
- 415
22
votes
2
answers
5k
views
If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?
Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku.
Can you treat this program as a black box and use this to solve ...
user101371
22
votes
3
answers
15k
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-...
- 1,115
21
votes
3
answers
10k
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 ...
- 1,587
21
votes
2
answers
5k
views
Is the "subset product" problem NP-complete?
The subset-sum problem is a classic NP-complete problem:
Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ that sums to $k$?
A student asked me if this variant of ...
- 9,007
21
votes
2
answers
5k
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 $...
- 537
20
votes
2
answers
5k
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 ...
- 683
19
votes
2
answers
4k
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-...
- 357
19
votes
2
answers
2k
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 ...
- 193
19
votes
1
answer
2k
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 ...
D.W.♦
- 152k
17
votes
1
answer
3k
views
Planarity conditions for Planar 1-in-3 SAT
Planar 3SAT is NP-complete. A planar 3SAT instance is a 3SAT instance for which the graph built using the following rules is planar:
add a vertex for every $x_i$ and $\bar{x_i}$
add a vertex for ...
- 12.4k
16
votes
2
answers
4k
views
Poly-time reduction from ILP to SAT?
So, as is known, ILP's 0-1 decision problem is NP-complete. Showing it's in NP is easy, and the original reduction was from SAT; since then, many other NP-Complete problems have been shown to have ILP ...
- 263
15
votes
3
answers
548
views
Minimal size of contracting a DAG into a new DAG
We have a DAG. We have a function on the nodes $F\colon V\to \mathbb N$ (loosely speaking, we number the nodes). We would like to create a new directed graph with these rules:
Only nodes with the ...
- 203
15
votes
2
answers
545
views
Is Hidoku NP complete?
A Hidoku is a $n \times n$ grid with some pre-filled integers from 1 to $n^2$. The goal is to find a path of successive integers (from 1 to $n^2$) in the grid. More concrete, each cell of the grid ...
- 537
15
votes
1
answer
278
views
Is There a Complete Problem for the Class of Turing Decidable Problems?
Languages such as $\text{HALT}_{TM}$ are $\textsf{RE-complete}$ under many-one reductions. It is trivial to see that $\text{co-RE}$ has complete problems, too. S. Schmitz [1] considers some classes ...
- 1,301
15
votes
2
answers
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}$. ...
- 365
14
votes
5
answers
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 ...
- 143
14
votes
2
answers
615
views
Does every NP problem have a poly-sized ILP formulation?
Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem ...
- 253
14
votes
1
answer
690
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\...
- 21.9k
14
votes
2
answers
3k
views
Reduction from 3-Partition problem to Balanced Partition problem
The 3-Partition problem asks whether a set of $3n$ integers can be partitioned into $n$ sets of three integers such that each set sums up to some given integer $B$. The Balanced Partition problem asks ...
- 4,387
13
votes
2
answers
3k
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 ...
- 483
12
votes
1
answer
10k
views
NP-complete proof from Dasgupta problem on Kite
I am trying to understand this problem from Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, chapter8, Pg281. Problem 8.19
A kite is a graph on an even number of vertices, say $2n$, ...
- 223
12
votes
1
answer
3k
views
NP-hardness of covering with rectangular pieces (Google Hash Code 2015 Test Round)
The Google Hash Code 2015 Test Round (problem statement) asked about the following problem:
input: a grid $M$ with some marked squares, a threshold $T \in \mathbb{N}$, a maximal area $A \in \mathbb{N}...
- 223
12
votes
1
answer
1k
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 ...
- 464
12
votes
1
answer
284
views
Are there any known AM-complete problems/is AM-complete well defined?
I'm curious about whether there are any complete problems in the Arthur-Merlin complexity class. Graph Non-Isomorphism (GNI) seems to be the canonical example of a problem in AM, but it's probably not ...
- 223
11
votes
2
answers
770
views
Is HORN-SAT in LIN, if so why is that not an indication that P=LIN?
The Complexity Zoo defines $LIN$ to be the class of decision problems solvable by a deterministic Turing machine in linear time.
$$LIN \subseteq P$$
Since HORN-SAT is solvable in $O(n)$ (as ...
11
votes
2
answers
10k
views
If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B
I'm studying for my final in theory of computation, and I'm struggling with the proper way of answering whether this statement is true of false.
By the definition of $\leq_m$ we can construct the ...
- 511
11
votes
1
answer
620
views
What do complexity classes look like, if we use Turing reductions?
For reasoning about things like NP-completeness, we typically use many-one reductions (i.e., Karp reductions). This leads to pictures like this:
(under standard conjectures). I'm sure we're all ...
D.W.♦
- 152k
10
votes
2
answers
5k
views
Mapping Reductions to Complement of A$_{TM}$
I have a general question about mapping reductions. I have seen several examples of reducing functions to $A_{TM}$
where $A_{TM} = \{\langle M, w \rangle : \text{ For } M \text{ is a turing machine ...
- 203
10
votes
1
answer
2k
views
Showing that minimal vertex deletion to a bipartite graph is NP-complete
Consider the following problem whose input instance is a simple graph $G$ and a natural integer $k$.
Is there a set $S \subseteq V(G)$ such that $G - S$ is bipartite and $|S| \leq k$?
I would like ...
- 2,430
10
votes
2
answers
3k
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 ...
- 71.8k
9
votes
4
answers
5k
views
How are all NP Complete problems similar?
I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps.
Prove that current problem is NP, i.e., given a certificate, prove
that it can be verified ...
- 309
9
votes
2
answers
5k
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)?
...
- 298
9
votes
3
answers
2k
views
Turing reducibility implies mapping reducibility
The question is whether the following statement is true or false:
$A \leq_T B \implies A \leq_m B$
I know that if $A \leq_T B$ then there is an oracle which can decide A relative to B. I know that ...
- 511
9
votes
1
answer
5k
views
What is the difference between turing reductions and many-one reductions?
To show that a particular language $A \in C$ is $C$-complete, where $C$ is some complexity class, we might construct a reduction from some known $C$-complete language $B$ to $A$, where $B$ is $C$-...
- 593
9
votes
2
answers
3k
views
Reducing max flow to bipartite matching?
There's a famous and elegant reduction from the maximum bipartite matching problem to the max-flow problem: we create a network with a source node $s$, a terminal node $t$, and one node for each item ...
- 9,007
9
votes
1
answer
1k
views
What NP decision problems are not self-reducible?
So we just learned about self-reducibility in class. My professor and our textbook would not commit to saying that all problems in NP are self-reducible, but there didn't seem to be any examples of ...
- 193
9
votes
2
answers
3k
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$...
- 309
8
votes
3
answers
9k
views
NP-completeness: Reduce to or reduce from?
Very simple question, but a mistake I make often enough that I'd love to have a standard reference.
I'm showing that a problem $P$ is NP-Hard by assuming I have a polynomial time algorithm to solve $...
- 29.5k
8
votes
3
answers
3k
views
SAT not reducible to 2SAT
Why is the reduction $\textbf{SAT} \leq_P \textbf{3SAT}$ possible, but $\textbf{SAT} \leq_P \textbf{2SAT}$ not possible, given, that $\textbf{SAT}$ is $\textbf{NP}$-complete, $\textbf{2SAT} \in \...
- 211
8
votes
2
answers
498
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.
- 414
8
votes
2
answers
7k
views
When problem A reduces to problem B, which problem is more complex?
When discussing complexity classes, when we say that problem $A$ reduces to problem $B$, are we saying that problem $A$ is at least as complex as problem $B$, or the other way around?
- 257
8
votes
2
answers
936
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 ...
- 1,368