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 ...
28
votes
0answers
793 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 ...
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 ...
24
votes
1answer
3k 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, ...
23
votes
2answers
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 ...
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 ...
21
votes
2answers
3k 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 ...
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 \...
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 ...
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-...
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 $...
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 ...
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 ...
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 ...
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-...
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 ...
15
votes
3answers
504 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 ...
15
votes
2answers
456 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 ...
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}$. ...
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 ...
14
votes
2answers
3k 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 ...
14
votes
1answer
228 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 ...
14
votes
1answer
2k 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 ...
14
votes
2answers
474 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 ...
14
votes
1answer
516 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\...
13
votes
2answers
2k 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 ...
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 ...
12
votes
1answer
152 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 ...
11
votes
2answers
548 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
1answer
2k 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}...
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 ...
10
votes
2answers
7k 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 ...
10
votes
1answer
1k 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 ...
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 ...
10
votes
1answer
333 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 ...
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)? ...
9
votes
1answer
4k 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$, ...
9
votes
1answer
1k views

Hardness and directions of reductions

Let us say we know that problem A is hard, then we reduce A to the unknown problem B to prove B is also hard. As an example: we know 3-coloring is hard. Then we reduce 3-coloring to 4-coloring. By ...
9
votes
2answers
1k 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
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$...
8
votes
3answers
613 views

Simple proof for NP-completeness of Edge Dominating Set

In a graph, an edge dominating set is a subset D of the edges such that any edge in the graph is either in D, or shares an endpoint with an edge in D. The Minimum Edge Dominating Set problem is to ...
8
votes
2answers
3k views

Graph 3-colorability is self-reducible

I am interested in self-reducibility of Graph 3-Coloralibity problem. Definition of Graph 3-Coloralibity problem. Given an undirected graph $G$ does there exists a way to color the nodes red, green, ...
8
votes
1answer
705 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 ...
8
votes
1answer
143 views

NP-hardness of finding a subset of vertices in a vertex-weighted graph

This is task from the German IT contest ("Bundeswettbewerb Informatik"), but since the deadline is past, asking this question is no cheating. Given a vertex-weighted, directed graph $G=(V, E)$ and ...
7
votes
3answers
957 views

The 'directionality' of reductions?

I've been finding myself a bit confused with the direction of reductions used to show that certain languages are not recursive. For example, let us say we want to determine if the Halting Problem ($...
7
votes
3answers
1k 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 ...
7
votes
2answers
817 views

Is SAT in P if there are exponentially many clauses in the number of variables?

I define a long CNF to contain at least $2^\frac{n}{2}$ clauses, where $n$ is the number of its variables. Let $\text{Long-SAT}=\{\phi: \phi$ is a satisfiable long CNF formula$\}$. I'd like to know ...
7
votes
1answer
899 views

Why does many to one reduction imply Turing reducibility?

So, $ A\leqslant_mB $ (many to one reduction) means that language $A$ can be reduced to language $B$ if there exists a Turing-calculable function $f$ so $ f(A) \subseteq B$ and $ f(\overline{A}) \...
7
votes
2answers
3k 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 ...