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

955 questions
Filter by
Sorted by
Tagged with
9 views

### Why can the construction of a polynomial-sized structure be done in logspace?

In paper http://www.iro.umontreal.ca/~mckenzie/Recherche/homc10fun.pdf the authors prove their problem is NL-complete. At some point in their proof however, they construct a polynomial-sized graph, ...
76 views

### Hardness of a scheduling/assignment problem

I am trying to prove the hardness of the following problem. This problem is from google hashcode, qualification-round, 2020. Hier is a brief description of the problem. Given a list or libraries and ...
77 views

### IS there a consensus on the definition of a computer program in CS literature and if so, what is it?

The following is what I came up with from my synthetic prior research but I might be wrong. I understand it is possible to reduce any computer "program", in a maximal reduction(?), to these features: ...
57 views

### Two versions of Subset Sum Problem

I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is: Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w_i$, ...
16 views

### Reducing vertex cover to minimal vertex cover

What is a quick and a elegant way to reduce vertex cover to minimal vertex cover? Is it possible to use vertex cover as verifier in the algorithm that reduces vertex cover to minimal vertex cover? ...
32 views

### Reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM}$

How to reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} =\{\langle M,w \rangle: M$ is a Turing machine that accepts $w$}. My try: Construct a ...
53 views

### why does $A≤_p \#SAT$ if $A \in BPP$

hello and thank you for helping me understand the following: I really don't understand this, why if language $A \in BPP$ then $A≤_P\#SAT$? language A is in BPP class, if for a probabilistic turing ...
95 views

### Polynomial-time linear-reduction from Directed Hamiltonian Path Problem to 3SAT

Is there a polynomial-time reduction from Directed Hamiltonian Path Problem to 3SAT which is linear in the number of vertices? That is, it reduces every directed graph $G$ with $n$ vertices to a ...
21 views

### Creating language $L_1$ with given parameter

Suppose $G$ is a context-free grammar, the language $L_0⊆\Sigma^*$ is also context-free but not-regular and $\#\not\in \Sigma$. Using $L_{(G)}$, $\#$, $L_0$, and $\Sigma^*$ create language $L_1$ such ...
30 views

### Is L decidable or not

Let $L = \{\lt M\gt | M$ is a $TM, L(M) = \{1^n0^n | n\ge0\}\}$. Create a reduction from $A_{TM}$ (acceptance problem) to $L$. Is $L$ not decidable? But isn't $L$ decidable since it is possible to ...
59 views

### Is the following fuction computable?

I'm trying to show that $K_1 \le_1 K$ where $K$ is the diagonal halting set $\{x : \varphi_x(x) \downarrow\}$ and $K_1=\{x: \exists y \,\, \varphi_x(y) \downarrow\}$, then I defined the function \...
47 views

### Is the number of NP-complete problems finite?

It should be straight forward to show that there are infinitely many NP-hard problems: Proof: Take the problem Remove 1 Vertex 3-COL ($R1V3COL$) which takes a graph $G=(V,E)$ as an instance and ...
33 views

### is L not decidable? [closed]

Let $L = \{\lt M\gt | M$ is a $TM, L(M) = \{1^n0^n | n\ge0\}\}$. Create a reduction from $A_{TM}$ (acceptance problem) to $L$. Is $L$ not decidable? But isn't $L$ decidable since it is possible to ...
25 views

### if there is no reduction from A to B

I'm facing the following question : If there is no $𝐴\leq_𝑚𝐵$ reduction, does this necessarily mean that A is not decidable? for any choice of B. thanks in advance.
51 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 ...
38 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...
17 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. ...
22 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 ...
162 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$ ...
27 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 ...
24 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 ...
19 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 ...
34 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?
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 ...
77 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 ...
39 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 ...
32 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 ...
137 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 ...
83 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 ...
134 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 ...
58 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 ...
49 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 ...
33 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 ...
120 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 ...
28 views

### Reductions from non decision problems

I want to show a minimization problem $Y$ has no approximation factor of 1.36. To be more specific the problem $Y$ is the exemplar distance problem between two genomes. Could I reduce from the min ...
60 views

### Partition into pairs with minimum absolute difference, NP-hard?

I have a set $S$ of an even number of positive elements $2m$ and $m$ values $t_1,t_2,\ldots,t_m$ where each $t_i\leq1$ for all $i$. The question is: can you select $m$ disjoint pairs $(a_i,b_i)$ from ...
66 views

### Can current quantum computers decide languages that Turing Machines cannot?

I am currently learning Computing Theory at university, and we were on the topic of Turing-Decidability, Recognizability, etc. Showing that a problem is undecidable with Turing machines due to ...
36 views

### How do I go about creating a mapping reduction?

So I understand what a mapping reduction is and how to create them for simpler problems such as a reduction from the set of even numbers to set of odd numbers however, seemingly more complicated ...
57 views

### Reduce duplicate subset sum problem to distinct subset sum problem?

In duplicate subset sum problem (DuSSP), we are given a multiset $\{a_1,a_2,\ldots,a_n\}$ where some of the $a_i$ are duplicates. We can assume that $a_1\leq a_2\leq \cdots\leq a_m.$ We are also given ...
55 views

### Clique-or-almost reduction to clique

I saw the posted question here about a direct reduction from near-clique to clique. Clique-or-almost is like near-clique but with the option for a complete clique of size $k$, I mean that perhaps an ...
16 views

### What are the requirements for a superset of P to be closed under karp reductions?

So today in our exercise session on complexity theory we discussed that P, NP, and BPP are closed under karp reduction. We also figured that the proofs could likely be expanded to straight ...
### If $Q$ reduces to $L$ then $\overline{Q}$ reduces to $\overline{L}$
The following exercise is taken from Chapter 17 of Languages and Machines by Thomas Sudkamp: Let $Q$ be a language reducible to a language $L$ in polynomial time. Prove that $\overline{Q}$ is ...