# 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,260 questions
Filter by
Sorted by
Tagged with
14 views

### Clique to SAT example explanation

We are at college trying to implement the reduction of the clique problem to a SAT problem but I dont quite get the examples of the slides if someone can give me a not so technical explanation of what'...
19 views

### Does valid value in L2 have to be gotten from L1 when we have a Many-One Reduction from L1 to L2

If I am doing a many-one reduction from L1 to L2, since it is described as a total function, does that mean that every possible encoding in L2 should have been achieved from L1 or is it possible that ...
28 views

### Can an unreocognizable language be Turing-reducible to a recognizable language?

Suppose $L_1\preccurlyeq_T L_2$, and $L_1$ is unrecognizable, can $L_2$ be recognizable? With decidability, if $L_1$ is undecidable, then $L_2$ is undecidable, because $L_1$ is the “easier” question. ...
41 views

### Reduction from novel problem to Set Cover

i would like to perform a reduction for my novel problem to preferably the set cover problem, but i am a bit lost.. My problem can be described as follows: Suppose you have given an binary word as ...
44 views

### Reductions to perfect matching

Can we reduce any well-known problems to deciding whether a (possibly non-bipartite) graph $G$ has a perfect matching? I'm particularly interested in finding a reduction from deciding whether a ...
203 views

### Showing this scheduling problem is NP-hard

I've been reading up on scheduling problems and the class of them that is NP-complete. Specifically, this is a foundational text on such problems, but the reductions are not clear to me. Can someone ... 1 vote
19 views

### Is $\Sigma_n^p$-SAT a complete problem for the $\Sigma_n^p$ class with polytime or with logspace reductions?

Here I define $\Sigma_n^p$-SAT to be the problem of deciding if a boolean formula in prenex normal form with $n$ alternating quantifiers, starting with $\exists$, is satisfiable. I found several ...
24 views

11 views

19 views

### proving or disproving a reduction from $R \leq P(Σ^*) \backslash RE$

I need to prove or disprove that for all languages in $R$ there is a reduction to all languages in $P(Σ^*)\backslash RE$. And I'm having trouble to figuring out the solution, especially with dealing ...
609 views

### Is it NP-hard to decide the existence of n subsets picked from n lists of subsets the union of which contains at most s elements?

You are given $n$ lists. The $i$-th list contains $k_i$ subsets of $\{1, \ldots, m\}$. You are also given an integer $s$. You should decide whether it's possible to pick up exactly one element (that ...
88 views

### Understanding reductions and notation

I am currently working through Sipser's Introduction to the Theory of Computation. In chapter 5, he defines that a Language $A$ is mapping reducible to language $B$, written $A\leq_m B$ if there is a ...
16 views

### Analogue of NP for oracle problems

I was just reading this question on the quantum computation stack exchange. It asks whether the HSP is in NP or not, and the answer notes that NP is a class of languages, not oracle problems. The ...
118 views

### System of equalities and inequalities is NP-hard using a reduction from 3COLORING

We are require to show that a problem where the input is a system of equalities and inequalities, each involving polynomials of degree at most 2 (with integer coefficients) in n real variables x1, x2,...
55 views

### Is there such a thing as $coW$-hardness?

I have a problem $\mathsf{A}$ and I would like to analyze its (parameterized) computational complexity. I found a parameterized reduction from the complement of the independent set ($\mathsf{coIS}$) ...
1 vote
34 views

### Concrete example of a set with a lower degree of unsolvability

Post's problem, posed in 1944 by Post, was to know if there is a recursively enumerable set, which, being undecidable, was not equivalent to the Halting problem under Turing reducibility. While I've ...
114 views

### How complement of ETM is semidecidable

If ETM = {＜M＞ ∣ M is a Turing Machine and L(M) = ∅}, how can I prove that the complement of ETM is semi-decidable?
36 views

27 views

### Reduction between a decidable language $L$ and $\Sigma^*$

Is there a reduction between a decidable language $L$ and $\Sigma^*$?
1 vote
77 views

### Correct defintion polynomial-time reduction

I have frequently seen two different definitions of polynomial-time reduction. In the following let $A, B \subseteq \Sigma^*$ be decidable problems. I will try to formulate the definitions in my own ...
28 views

### If $B \in RE$ then $A \in RE$ - Reduction

I know that if there is a Turing Reduction from $A$ to $B$, say $A \le_T B$, and $B \in R$ then $A \in R$. I also know that Turing Reduction is for Decision, and not Recognition. Is it possible to ...
34 views

54 views

### Reduction from Diophantine Equation Problem to Halting Problem

I want to study the reduction from the Diophantine Equation Problem (Hilbert's tenth problem) to the Halting problem. Can you either explain it to me or give me a credible source from which I can ...
173 views

### Is this sorting problem NP-complete?

Consider array $A=(a_1,a_2,...,a_n)$ such that $a_i$s are positive integers. Moreover, we have $k$ binary tuples, each with length $n$. In each iteration, we choose one of those tuples, and decrease ...
1 vote
Let $L$ be an arbitrary language in $\Sigma_3$. Thus it can be written that $x \in L \Leftrightarrow \exists y^{p(|x|)} \forall z^{p(|x|)} \exists w^{p(|x|)} \langle x,y,z,w \rangle \in B$ where $p(\... 0 votes 0 answers 46 views ### Equivalence for Turing Machines is not Recognizable - Reduction DOUBT I have a big doubt on this video about$EQ_{TM}$, especially on minute 5:11. Why is he saying that to reduce$ A_{TM}\lt_{m}\overline{EQ_{TM}} $we need to create a machine M that rejects every input? ... 1 vote 1 answer 32 views ### Reduction from$2$-Partitioning to (simple) pairwise$2$-Partitioning I'm currently stuck showing$NP$-hardness of a problem of mine. An instance of my problem (I call it (simple) pairwise$2$-Partitioning) is given by the following: Given a set of tupels$B=\{(b_1,1),\...
Let $\varphi = \bigwedge C_k$, in which $C_k$ is a clause in X3SAT (exactly-one 3SAT or one-in-three 3SAT). That is, $C_k = (l_i \odot l_j \odot l_u)$ such that $l_i \in \{x_i, \overline{x}_i\}$ for ...