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
5
votes
1answer
827 views

Anti-symmetry of polynomial time reductions

I read somewhere that, if $A\leq_p B$ and $B\leq_p A$, then it is said that $A\equiv_p B$. What exactly does this mean? Is it saying that both $A$ and $B$ are the exact same level of complexity?
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 ...
4
votes
1answer
632 views

What is the difference between these terms?

Between my textbook and various online sources (namely wikipedia), I'm very confused... can somebody clear up which words are synonymous and which mean different things? Many-to-one reduction Mapping ...
2
votes
1answer
296 views

How do I explain that a polynomial time reduction is in fact polynomial time?

I have as an assignment question to show that $QuadSat=\{\langle\phi\rangle\mid\phi$ is a satisfiable 3CNF formula with at least 4 satisfying assignments$\}$ is $\sf NP$-Complete. My solution is as ...
1
vote
1answer
162 views

Polynomial time reductions

I'm having a very hard time understanding what's what. $$L_{1}\leq_{p}L_{2}$$ If $L_2$ is stated to be in $\textbf{NP}$, is it necessarily true that $L_1$ is $\textbf{NP}$-Complete? I need to show ...
5
votes
1answer
501 views

Definition of Strongly Parsimonious Reduction

There is a well known definition of parsimonious reduction. The standard definition of parsimonious reduction is very intuitive. It simply means that the two problem have the same number of solutions,...
3
votes
1answer
2k views

HamCycle to HamPath reduction

I've seen a reduction that's done by adding another vertex to the graph and creating a path through that vertex. Why do I need to add a vertex? Cant I just remove an edge? Lets say the graph with the ...
5
votes
2answers
895 views

Problems that are Cook-reducible to a problem in NP $\cap$ co-NP

Let $\mathcal{A}$ be a problem in $\text{NP} \cap \text{co}$-$\text{NP}$. Now assume we can reduce another problem $\mathcal{B}$ to it using Cook reduction. What conclusions can we draw about $\...
3
votes
2answers
169 views

Does reduction from an NP-complete problem to some problem $X$ imply that $X\in NP$?

I am having problems resolving the following question: Given some problem $X$. If there exists a polynomial time reduction from (for example) $\mbox{SAT}$ to $X$, $(\mbox{SAT} \leq_{p} X)$ and ...
2
votes
1answer
748 views

NAE SAT reduction to weighted MAX CUT

I am trying to reduce NOT-ALL-EQUAL SAT to MAX-CUT with weighted edges. I know that if there are weights to the edges, then I can reduce NOT-ALL-EQUAL SAT to MAX CUT by have a $G$ with $2n$ nodes ($...
3
votes
1answer
177 views

Why does $A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon$?

I have a book that proves the halting problem with this simple statement: $$ A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon $$ It states that halting problem reduces to the ...
5
votes
2answers
208 views

Language comprising of Turing machine encodings

Let $A$ be the language $\{\langle M\rangle\mid M\text{ is a Turing machine that accepts only one string}\}$ According to my understanding, if a Turing machine is able to decide if another Turing ...
1
vote
1answer
4k views

Proving that the clique cover problem is in NPC by reducing from k-coloring

Provided that we have to compare it against the graph coloring problem which is NPC. So far, I can only think of connecting edges from a vertex in a provided graph to all the other edges it is not ...
7
votes
3answers
327 views

Is there a simple example of sets such that $A \leq_T B$ but not $A \leq_m B$?

I wonder if there is a simple example of sets $A$ and $B$ such that $A$ is Turing-reductible to $B$ but not many-to-one reductible to $B$.
1
vote
2answers
801 views

Reducing a problem to Halt

I'm reviewing for a computability test, and my professor has not provided solutions to his practice questions. I came up with a "solution" to this problem, but it really seems like my answer is wrong (...
2
votes
2answers
414 views

Implications of polynomial time reductions

I'm reviewing for finals and have a sample problem that I think I understand, but would like someone to bless my understanding or smack me and tell me why I'm wrong. I'm presented with a problem $\Pi$...
1
vote
2answers
526 views

NP-complete reductions

I've read that "Every problem in NP can be reduced to every NP-complete problem". My question is on the choice of the word "reduce". If I were to "reduce" a polynomial problem in NP to an ...
4
votes
2answers
528 views

Proof for P-complete is not closed under intersection

Unfortunately I have no idea how to show this: Show that the set of ${\sf P}$-complete languages is not closed under intersection. As far as I understand my lecture notes, ${\sf P}$-completeness ...
0
votes
1answer
516 views

How to determine the polynomial runtime of an NP reduction?

To show that a NP problem is NP-complete, we also have to show that $L \leq_{p} L'$ , where $L$ is proven NP-complete and you have to prove $L'$ also is. The thing I am confused is how in all NP-...
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 ...
2
votes
2answers
117 views

Optimization-factoring $\le_p$ Decision-factoring

Optimization factoring: Input: $N\in \mathbb{N}$ Output: All prime factors of $N$ Decision factoring: Input: $N, k\in \mathbb{N}$ Output: True iff $N$ has a prime factor of at most $k$ How can I ...
2
votes
1answer
2k views

reducing subset-sum to partition

Subset-sum: Given a list of numbers, find if a non-empty sublist has sum 0 (there's a variation where we want sum=k instead of 0, but 0 is easier for analysis) Partition: Given a list, can it be ...
1
vote
1answer
2k views

Showing a partition-like problem is NP-complete

Given a set $A=\{a_{1},a_{2},a_{3},\ldots,a_{n}\}$, then construct a set $P=\{p_{1}, p_{2}, p_{3}, \ldots , p_{n}\}$ such that $|p_{i}|=a_{i}$, and $\sum_{i = 1,}^{n}p_{i} = 0$. This problem is NP-...
5
votes
2answers
1k views

Reduction to Hamiltonian cycle

Given that the Hamiltonian cycle problem is NP-complete, I want to prove that the following problem is NP-complete: Given an undirected graph $G(V,E)$ and vertices $s,t\in V$, does there exist a ...
2
votes
2answers
2k views

Find an undecidable language that is mapping-reducible to its complement

As the title suggests. Also, such a language must satisfy that neither it nor its complement are semi-decidable. I already know that $All_{TM}, EQ_{TM}, T$ (that is the set of all deciders) satisfy ...
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 ...
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 \...
2
votes
1answer
221 views

Reduction of A_LBA to E_LBA

I have a rather interesting one to ponder and would love if I could get an answer for it. We were discussing the topic of mapping reduction today in my Computing theory course and I was wondering why ...
2
votes
1answer
1k views

Polynomial time reducibility

$L_1$ and $L_2$ are two languages defined on the alphabet $\sum$. $L_1$ is reducible to $L_2$ in polynomial time. Which of the following cannot be true? $L_1 \in P$ and $L_2$ is finite $...
14
votes
1answer
536 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\...
1
vote
0answers
70 views

How to reduce MaxUNSAT to MaxSAT in a (almost) direct way?

In question How to reduce MaxUNSAT to MaxSAT? I was asking, how to reduce the MaxUNSAT problem to MaxSAT. With help of the given answer I could give a polynomial reduction : $MaxUNSAT \leq ...
5
votes
1answer
1k views

Understanding the definition of reduction

From Wikipedia: Given two subsets A and B of N and a set of functions F from N to N which is closed under composition, A is called reducible to B under F if $$ \exists f \in F \mbox{ . } \...
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
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)? ...
4
votes
1answer
2k views

Reducing TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SAT

In Cormen's Algorithms book on NP-completeness they prove various problems are NP-complete by reducing a previously proved NP-complete problem (call $K$) to current problem (call $L$). Each proof ...
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$, ...
4
votes
2answers
2k views

How to reduce to an NP-hard problem?

For an assignment I have to program an application to schedule conversations. There is an event where representatives of the elementary schools talks with the representatives of high schools. They ...
5
votes
1answer
7k views

Reduction from set cover problem to vertex cover problem

Although the reduction from vertex cover problem to set cover problem is quite simple, I did not find anywhere the reduction in the opposite direction. From the similarity in the type of problems, I ...
1
vote
1answer
50 views

Produce decision version of the problem

An optimisation problem requires minimising some function $f(x)$, where $x$ is a vector of integers. What is the corresponding decision version of the problem?
3
votes
1answer
261 views

Can an exponential algorithm for an NPC problem be transformed into an algorithm for other NP problems in polynomial time?

After looking at other questions and my textbook, I seem to get some confusion. I do get that when there is a polynomial algorithm of NPC, there is a polynomial algorithm for a NP problem. But the ...
5
votes
0answers
229 views

Find a permutation that maximize the minimum of $\frac{a_n}{a_{n-1}} + \frac{a_n}{a_{n+1}}$

Consider a sequence of $n$ positive real numbers $a_0,\ldots,a_{n-1}$. Let $S_n$ be the set of permutations on $\{0,\ldots,n-1\}$. We are interested to find $$ \max_{\pi\in S_n}\left( \min_{i=0}^{n-...
2
votes
1answer
701 views

Showing that the set of TMs which visit the starting state twice on the empty input is undecidable

I'm trying to prove that $L_1=\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q_0 \text{ at least twice on } \varepsilon\} \notin R$. I'm not sure whether to reduce the halting ...
5
votes
1answer
4k views

Is MAX-SAT NP-hard?

Is the MAX-SAT problem NP-hard? From the Wikipedia page: The MAX-SAT problem is NP-hard, since its solution easily leads to the solution of the boolean satisfiability problem, which is NP-complete ...
5
votes
1answer
270 views

The $\text{k-key}$ problem

Given an undirected graph, I define a structure called k-key as a path containing $k$ vertices which are connected to a simple cycle which contains $k$ vertices as well. Here's the k-key problem: ...
7
votes
2answers
826 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 ...
5
votes
1answer
726 views

Reduction to equipartition problem from the partition problem?

Equipartition Problem: Instance: $2n$ positive integers $x_1,\dots,x_{2n}$ such that their sum is even. Let $B$ denote half their sum, so that $\sum x_{i} = 2B$. Query: Is there a subset $I \...
1
vote
1answer
2k views

Solve a problem through reduction

I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard). Let's assume that you have proven that ...
4
votes
3answers
471 views

Are there complete problems for P and NP under other kinds of reductions?

I know that the complexity class $\mathsf{P}$ has complete problems w.r.t. $\mathsf{NC}$ and $\mathsf{L}$ reductions. Are these two classes the only possible classes of reductions under which $\...
8
votes
2answers
657 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 ...
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 ...