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

954 questions
Filter by
Sorted by
Tagged with
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?
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 ...
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 ...
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 ...
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 ...
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,...
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 ...
895 views

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 ...
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 ...
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 ...
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$.
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 (...
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$...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
2k views

536 views

1k views

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 ...
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 ...
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: ...
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 ...
726 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 ...
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 ...