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

1,022 questions
Filter by
Sorted by
Tagged with
34 views

### how does Kleene-Post show two languages that are not Turing reducible to each other?

I'm having difficulty understanding the proof of the Kleene-Post result. It purports to construct two languages that are not Turing reducible to each other, using a diagonalization argument. I've seen ...
105 views

### Reductions among two problems related to walks of length $k$

Consider the following two problems: A. Given a directed graph and a parameter $k$, determine if it contains a path (not necessarily simple) of length $k$. B. Given a directed graph, two vertices $s,t$...
17 views

### If two languages are decidable, can one be mapping reducible to the other?

If I have two decidable languages $A$ and $B$, is $A \leq_m B$ true? How would I show this?
29 views

### Why are $L$-reductions defined the way they are?

I was reading about $L$-reductions and there was one part in the definition that I thought was interesting. I wanted to know what motivated people who came up with it to have it included in the ...
51 views

### What is the polynomial time reduction between these two Hamiltonian cycle problems?

Problem 1: Given an undirected graph, return the edges of a Hamiltonian cycle, or correctly decide that the graph has no such cycle. Problem 2: Given an undirected graph, decide whether or not the ...
38 views

### Finding the smallest-cost way to deliver goods

I want to deliver products from various sources to various destinations such that the overall cost is minimized. We need to deliver these products while obeying our contractual obligatione with each ...
87 views

### Playing video games to solve SAT instances

This paper shows that computer games, such as Super Mario, are NP-hard, by reduction from SAT. It may be possible to use this reduction to help solve hard instances of SAT: use the reduction to ...
47 views
+50

### Reduction from 3-partition to ABC-partition

The ABC-partition problem is a variant of 3-partition in which, instead of a single set $S$ with $3 m$ positive integers, there are three sets $A, B, C$ with $m$ positive integers in each. The goal is ...
74 views

### 3-partition problem without the restriction to triplets

In the standard 3-partition problem, there are $3 m$ integers, their sum is $m T$, and they have to be partitioned into $m$ subsets of sum $T$ and size $3$. Consider the variant without the ...
12 views

### Is there a fpt reduction of a NP-hard problem towards a fpt parameterisation $K'-D' \in FPT$?

Question While trying to search for a (example of a) NP-hard problem that fixed-parameter reduces to another NP-hard problem that is known to be fixed parameter tractable, such as k-Vertex Cover, my ...
125 views

### NP-completeness of a Generalized Version of Subset Sum

I am curious about the NP-completeness (or if not, an efficient algorithm) for the following generalization of the subset sum problem: In subset sum, we are given a number $t$ and a collection $S$ of ...
84 views

38 views

### Show that for every language there exists a harder language

I came across this problem that I could not figure out... For every language $A$, there is supposed to be a language $B$ such that: $$A \leq_T B$$ but: $$B \not \leq_T A$$ If it is $A \leq_TB$ and ...
22 views

### reduction of independence problem and cluster problem

independent problem is: there is a simple and undirected graph, we are looking for the maximum vertex in which there is no edge between any two of them. cluster problem is: there is a simple and ...
31 views

### Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$

I'm having a small issue with wikipedia's proof that $RP \subseteq NP$: An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic ...
54 views

### Variant of Subset-sum has an $O(1)$ algorithm if $Goldbach$ is true

Given $S$ of positive integers $>$ $1$ is there some combination with even $SUM$ > $2$ that is NOT the sum of two primes? $SUM$ = 10 $S$ = $[4,6]$ $No$, Sum of Two Primes $5 + 5 = 10$. ...
48 views

### What does “If P1 is reduced to P2, then P2 is at least as hard as P1” mean?

I am having trouble understanding the following statement regarding Turing reduction: "If P1 is reduced to P2, then P2 is at least as hard as P1." Does this mean that (i) P2 can be harder ...
24 views

### mapping reductions from R to RE

Let $L_1$ be some language in $R$. Let $L_2$ be some language in $RE$. Is it necessarily that $L_1 \leq_m L_2$ ? I know that for non trivial $L_1$,$L_1$ in $R$ it is right to say that $L_1 \leq_m L_2$....
30 views

### proving existence of TM that accepts the next language

I have an idea of how to approach the problem, but I'm not sure about it. Given a Turing Machine, I can check how many states the machine has, and somehow by the number of states to know if the run ...
81 views

16 views

### Redcue CFG-Eequiv to CFG-SYM [duplicate]

I want to show, that for an CFG G the question wether $L(G)=L(G)^R$ is undecidable. My first try was to reduce from the CFG-Equivalent Problem) $CFG_{EQUIV}\leq CFG_{SYM}$. My first attempt was to ...
64 views

### How to prove NP-Completeness of longest path between two vertices relying Hamilton NP-Hard problem

I have this question: I have an undirected graph G(V, E) (where V = set of vertices, E = set of edges). Consider the maximum path between two vertices s and t: ...
75 views

### Close To Cook Reduction given NP != coNP

I am struggling to answer these two questions: Prove or wrong: Both are given the assumption that NP != coNP. For any 2 decision problems S, S', if there is a Cook reduction from S' to S then there ...