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

942 questions
Filter by
Sorted by
Tagged with
35 views

### What is the result of a reduction operation called?

Is there a commonly used term for the result of a reduction operation? "reductant" does not quite sound right...
40 views

### Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?

Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k) polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a ...
147 views

### Undecidability of two Turing machines acting the same way on an input

So I need to find a reduction to the (undecidable) problem of deciding if two Turing machines $M_1$ and $M_2$ behave the same way on an input $x$. "Behaving the same way" is defined like this: $M_1$ ...
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 ...
3k 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 ...
21 views

### From 2IN3SAT to NAE3SAT ( not all equal )

We know that 1IN3SAT is np-complete , I will define an ne form of the SAT problem 2IN3SAT (exactly two true variables ). 2IN3SAT is np-complete because (x,y,z) is in 1IN3SAT iff (!x,!y,!z) is in ...
16 views

### Proof by reduction that the Universal Language is not recursive using the complement of the Diagonalization language

I have the following proof which I don't fully understand. L D/ is the complement of the Diagonalizaton Language. L U is the Universal language. Assume U* is a TM for Lu which always halts. ...
130 views

### Is Finding A Hitting Set of Size n/2 NP-Hard?

In Hitting Set problem we are given a collection E of subsets of V and we want to find smallest subset H of V which intersects (hits) every set in E. In decision version of the problem, we are asked ...
661 views

### Condensed Nearest Neighbor Explanation

I have a question regarding the Condensed Nearest Neighbor algorithm from ...
25 views

### In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects?

Let HALT be the language $\{\langle M, w\rangle : M\text{ is a TM that halts on }w \}$. Let ALLHALT be the language $\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\}$. Use a reduction ...
20 views

### reduction: L1’s decidability is unknown and L2 is undecidable

About this question: Reductions can be tricky to get the hang of, and you want to avoid “going the wrong way” with them. In which of these scenarios does L1 ≤m L2 provide useful information (and ...
20 views

### Proving Problems are Undecidable/ Semi decidable? E.g. Halting Problem, Membership Problem? [duplicate]

I am having issues finding similarities in different cases where a problem such as the Halting Problem or the Accept-Λ problem is reduced to the Membership problem to prove that it is semi-decidable ...
15 views

### Polynomial reduction proprietries: reflexive, transitive, but not symmetric

From theory I know the polynomial reduction is: reflexive $A ≤ A$ (A Language) transitive $A ≤ B$ and $B ≤ C$, then $A ≤ C$ (A, B, and C Languages). What about symmetric? There is an example with ...
121 views

### Invertability of Karp reductions

Karp reducibility between NP-complete problems $A$ and $B$ is defined as a polynomial-time computable function $f$ such that $a \in A$ if and only if $f(a) \in B$. I am interested in polynomial-time ...
58 views

### On FPTAS and many one parsimonious reductions

We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction. If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have? If $\Pi_2$ has an ...
73 views

### Are there any problems that reduce to the halting problem?

I'm reading through sipser and there is a lot of computability problems that the halting problem reduces to, i.e. if $A_{TM} = \{\langle M,w\rangle : M$ accepts input $w\}$ then $A_{TM} \leq P$ where ...
32 views

### Complexity problem reduction?

Let say A and B are two decesion problems where A $\le$ B polinomial reduction is true. Is this : A̅ $\le$ B̅ also true? If so, can you show an exemple, if not why?
57 views

### Given a set, partition it into ordered triples

I have a set $S$ of $3m$ positive numbers $\{a_1,a_2,\ldots,a_{3m}\}$. The question is: can you select $m$ disjoint triples $(a_i,a_j,a_k)$ from $S$ such that $a_i-a_j-a_k\geq1$? I was trying to ...
176 views

### Circuit satisfiability problem : SAT-C to SAT-2C

I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C. Prove that ...
29 views

### Can polynomial many-to-one reduction be done to a specific problem instance?

Let's say I reduce the problem $A \in L$ to $B \in K$ , with a function $f: \Sigma^{*} \rightarrow \Gamma^{*}$ such that $w \in L \Leftrightarrow f(w) \in K$ . I know if I want to solve $A$, given ...
51 views

### Multivariate polynomials

Given a Diophantine equation $p(x_1,x_2,...,x_n)$, Can I find a reduction from $\text{dioph}(\mathbb{N}) \leq \text{dioph}(\mathbb{N}_e)$? $\mathbb{N}_e$ is the set of even numbers. So I have to ...
75 views

### NP-completeness for integer linear program

This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come ...
45 views

112 views

### How do I reduce subset sum to another problem in NP?

I'm trying to solve the following problem about arranging pens on rows. The problem goes as the following. Given $n$ integers $l_1, \dots l_n$, the lengths of the pens, r rows and a goal G. Is it ...
37 views

### Hamiltonian cycle, verifying and finding

If we have an algorithm that in polynomial time says if a graph G has an hamiltonian cycle, can we have an algorithm that in polynomial time find an hamiltonian cycle? My attempt is to delete an edge ...
29 views

### Reducing universal language to language of palindromes

I am trying to understand proof for proving language of all palindromes is undecidable from these slides. It tried to reduce universal language to language of all palindromes on alphabet. The two ...
11 views

### Decide if Turing machine's language contains either a or b string

during school exercises we worked on decidability problems and there was one I don't really understand. We were provided with solution and explanation regarding this exercise but still I need more ...
63 views

### NP-hardness even with perturbations

Consider the following problem, which can be called "2-SET-PARTITION": Given two sets of positive numbers, $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$, where $\sum_{i\in[n]}a_i = \sum_{i\in[n]}b_i = 2 S$,...
100 views

### Reduction from Vertex Cover to Dominating Set

I am trying to reduce the vertex cover (decision) problem to the dominating set (decision) problem in order to prove that the latter is NP-hard. After some research online, I found that many articles ...
46 views

### How do we construct reductions for NP-Completeness

I'm wondering in what direction we construct reductions to prove that a problem is NP-complete. Say the question is asking to prove that the vertex cover problem is NP-complete given that the ...
119 views

### Example of two undecidable languages that cannot be reduced to each other

I want to find two undecidable languages $A$ and $B$ that $A$ cannot reduce to $B$, $B$ cannot reduce to $A$(Many-one reduce). One of my thought is to let $A$ be the halting problem, let $B$ be some ...
113 views

### Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete?

I have a graph with at most two outgoing arcs for each node and I need to extract a DAG by removing the least number of arcs. I know that the general problem is np-complete but i can't reduce it to ...
32 views

### Why does such reductions work [duplicate]

In class we saw examples of reductions like from Independent Set (IS) to Longest common subsequence (arbitrary number of sequences) (LCS) $V = \{v_1,\ldots,v_n\} E =\{ e_1,\ldots, e_m \}$ The ...
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, ...
270 views

### Solving the min edge cover using the maximum matching algorithm

To solve an instance of an edge cover, we can use the maximum matching algorithm. Edge Cover: an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least ...