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

Filter by
Sorted by
Tagged with
0 votes
0 answers
13 views

"Term Rewriting and All That" - Exercise 2.3

I am working through the exercises in the book "Term Rewriting and All That" and got stuck on question 2.3. The question reads: find a reduction $\rightarrow$ on $\mathbb{N}$ such that $\...
Ruben Hensen's user avatar
0 votes
0 answers
19 views

Help understanding the proof that $L = \{ \langle M \rangle \mid M \text{ is a TM that accepts the input string } 101\}$ is undecidable

I understand of the existence of Rice's Theorem, however, I want to understand better how this reduction is formed. My professor gives the answer as follows: "By contradiction, assume that $L$ is ...
codeing_monkey's user avatar
0 votes
0 answers
27 views

Karp-reduction of Disk Covering Problem

While preparing for final exam, I encountered a (target) problem where you have $M$ lines and $L$ points and you want to answer if it's possible to cover them all using $K$ disks of unit radius (...
girish's user avatar
  • 3
0 votes
0 answers
23 views

Proving $A_{TM}$ is mapping reducible to certain language

I've been asked to prove that the language $A_{TM} = \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$ is mapping reducible to the language $LOOP-ONE = \{\langle M \rangle \mid M$ is a Turing ...
Yarin's user avatar
  • 229
-1 votes
0 answers
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'...
user164639's user avatar
0 votes
0 answers
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 ...
River Uzoma's user avatar
0 votes
1 answer
30 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. ...
Arthur's user avatar
  • 3
0 votes
0 answers
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 ...
Sven Fiergolla's user avatar
0 votes
1 answer
48 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 ...
dsjoint's user avatar
0 votes
1 answer
219 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 ...
user avatar
1 vote
0 answers
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 ...
Turambar's user avatar
0 votes
0 answers
24 views

Is PAD(EXP) = P?

Can I say that all languages in the class $\textbf{P}$ are just a padded version of some other problem in $\textbf{EXP}$? I am familiar with the padding argument, which states that if $\textbf{P} = \...
Zeeshan ahmed's user avatar
3 votes
1 answer
37 views

EXP reduction to show NEXP-completeness

I wonder why can't I allow an exponential-time reduction from all problems in $\textbf{NEXP}$ to a language $L$ and claim $L$ to be $\text{NEXP-complete}$. The computational complexity class $\text{...
Zeeshan ahmed's user avatar
0 votes
0 answers
11 views

$UCOUNT\leq_{cd} BCOUNT$

Suppose we are given $n$ bits $a_0,\dots, a_{n-1}$. Then let $s=\sum\limits_{i=0}^{n-1}$ Then $BCOUNT(a_0,\dots,a_{n-1})=s$ and $UCOUNT(a_0,\dots,a_{n-1})=1^s0^{n-s}$ Now i have to show that $UCOUNT\...
Soham Chatterjee's user avatar
-1 votes
2 answers
50 views

Show that the language is undecidable

Consider the language L = {< M >| M accepts iff input length is divisible by 3}. I'm supposed to use reduction to show that the language is undecidable. I tried proving it but didn't know what ...
berlin23's user avatar
0 votes
0 answers
22 views

Reduce A ∶= {x ∈ N ∣ x < 10} to Halting Problem on empty tape

I am preparing for an exam in computability and still learning about the idea of reductions. I found an interesting problem to start with and am curious if my approach is correct: Let H0 be the ...
dport's user avatar
  • 1
0 votes
1 answer
127 views

reduce independent Set into independent Set of distance 4 between all vertices

I want to prove the following problem is NP-complete: 4-Spaced-Set: Assume you have a undirected graph $G=(V,E)$, and a positive integer $k$. Let's say a set of vertices $A \subseteq V$ is $4$-spaced ...
andydandy 's user avatar
-2 votes
1 answer
27 views

Is this considered a vertex cover?

I'm unsure if this satisfies the definition of vertex cover, the graph is unweighted and undirected: if not, an explanation would be super enlighting.
Aishgadol's user avatar
  • 315
1 vote
1 answer
99 views

Reduction from MAX-3-CUT to MAX-CUT

Both MAX-CUT and MAX-3-CUT are known to be NP-complete. This post shows a reduction from MAX-CUT to MAX-3-CUT. I am curious if there is a way to reduce MAX-3-CUT to MAX-CUT? MAX-CUT: Given an ...
Phasivio's user avatar
  • 113
2 votes
1 answer
76 views

How to reduce $k$-oriented problem to max flow problem?

Given an undirected graph $G$, how to reduce this problem :"Judge whether every edge of $G$ can be given a orientation such that for every vertex $v$ in $G$ has input-degree of at most $k$" ...
qmww987's user avatar
  • 123
-1 votes
1 answer
44 views

if there is a 3/2 approximation algorithm for independent set then there is a 3/2 approximation algorithm for vertex cover?

if by absurdly there is a 3/2-approximation algorithm for INDIPENDENT SET then does there exist a 3/2-approximation algorithm for VERTEX COVER? the implication should be true because independent is ...
PatrickBateman's user avatar
0 votes
1 answer
47 views

Reduction from a language with unknown decidability to HALT

We were taught to use reductions in order to show that a given L is undecidable. My question is, given some definition of a new L, is there a way to find a reduction $$ L\leq_mHALT $$ So that I can ...
John's user avatar
  • 1
0 votes
0 answers
12 views

Existence of a Path from Initial to Accepting Configuration in Turing Machine Runs: A Reduction-Based Proof

Is it possible to show, by reduction(Reduction in the length of the path and the running time), that for a Turing machine M and an input X, there exists a run in which M accepts X if and only if there ...
Lupital's user avatar
0 votes
1 answer
49 views

L = {⟨M⟩ : there does not exist w ∈$Σ^*$ such that M rejects w } is in coRE?

given this lanauge: $L=\left\{\langle M\rangle\right.$ : there does not exist $\mathrm{w} \in \Sigma^*$ such that M rejects $\left.\mathrm{w}\right\}$. how can I determine whether it is in $R, R E \...
user1701057's user avatar
0 votes
0 answers
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 ...
yoav's user avatar
  • 1
2 votes
2 answers
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 ...
Vladislav Bezhentsev's user avatar
-1 votes
1 answer
89 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 ...
talon23's user avatar
0 votes
0 answers
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 ...
Andrew Baker's user avatar
0 votes
1 answer
122 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,...
staz6's user avatar
  • 25
3 votes
0 answers
59 views

Is there such a thing as $coW[1]$-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}$) ...
nuss_ecke's user avatar
1 vote
1 answer
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 ...
user6767509's user avatar
0 votes
1 answer
125 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?
Essie's user avatar
  • 1
0 votes
2 answers
38 views

How can a $P(n)$ run in polynomial time if it calls $R(m)$ which has exponential time

We have a procedure $P(n)$ that makes multiple calls to a procedure $Q(m)$, and runs in polynomial time in n. Unfortunately, a significant flaw was discovered in $Q(m)$, and it had to be replaced by $...
Pratik Hadawale's user avatar
4 votes
2 answers
102 views

Do all NP-hard problems have a reduction from one to another (Either A $\leq_m$ B or B $\leq_m$ A)

Given two problems, $A$ and $B$, that are NP-hard. Is either one of the following is true? $A \leq_m$ B $B \leq_m$ A In other words, is there always a relationship between any two arbitrary NP-hard ...
Andrew Baker's user avatar
0 votes
3 answers
163 views

Sorting Numbers in O(N)?

Why is sorting numbers Omega(nlogn)? I'm thinking of an reduction algorithm where: For all the numbers x_i, we create a point (x_i, 0) on a 2d graph. Fit a line directly to the right starting from ...
Mike Rain's user avatar
0 votes
0 answers
41 views

How do Turing machines output $f(w)$ for $O(1)$ reductions?

When speaking about many-one Karp reductions, the definition is stated below: $$ A \leq_P B \iff \exists f \colon \: \Sigma^* \mapsto \Gamma^* \: \text{such that} \: (w \in A \iff f(w) \in B) $$ where ...
Ank i zle's user avatar
  • 153
2 votes
1 answer
60 views

Is finding a Polytime reduction from $L_1$ to $L_2$ equivalent to proving $L_2 \in P \Rightarrow L_1 \in P$

I often hear NP-completeness as problems such that, if they were in $P$ all problems in $NP$ are in $P$. The true definition, though, is that NP-complete is a set of languages in NP that all languages ...
Ank i zle's user avatar
  • 153
0 votes
1 answer
41 views

Do reductions (in NP and other classes) follow a linear path?

NP has several complete problems, which reduce to one another. In this sense, they are all "equal" in terms of hardness. There are other problems in NP that are also "equal" to one ...
Loic Stoic's user avatar
0 votes
0 answers
34 views

Reduction between problems where problem A solves problem B with probability $\frac{2}{3}$

Suppose we have a problem, $A$, and a machine $T_A$ that solves $A$. Now, let's say we have a problem $B$ that is solvable with a polynomial number of calls to $T_A$, and we call $T_B$ the machine ...
Loic Stoic's user avatar
0 votes
1 answer
84 views

Possible reduction from SUBSET-SUM

Given is a multiset $S$, a finite set $T = \{t_1, t_2, t_3\}$, and an integer $k \in \mathbb{N}$. Let $v(t_j)$ be a set of values $\in \mathbb{R^+}$ of length $|T|$ that can be assigned to $s_i$, and $...
joachimkristensen's user avatar
0 votes
0 answers
28 views

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

Is there a reduction between a decidable language $L$ and $\Sigma^*$?
fva's user avatar
  • 1
1 vote
1 answer
87 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 ...
Polgerta's user avatar
0 votes
1 answer
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 ...
Geo's user avatar
  • 37
0 votes
1 answer
35 views

Prove by reduction that language of TMs accepting only words starting with 101 is undecidable

Before an exam in Computability I go through questions from last year's test. So the question is: $$A= \{ \langle M\rangle x | M \text{ is a TM and accepts } x \}$$ $$ L = \{ \langle M \rangle | M \...
Konstantin's user avatar
0 votes
0 answers
63 views

Is $L(M_{A_{TM}⤭})$ NP-Hard?

Let $A_{TM}=\{<M,w>|M~is~a~TM~and~M~accepts~w\}$, clearly it is NP-Hard. Let $M_{A_{TM}}$ be the DTM that recognizes $A_{TM}$. Define $M_⤭$ to be the TM obtained from $M$ by swapping the accept ...
Geo's user avatar
  • 37
2 votes
0 answers
27 views

Are $\mathsf{L,NL}$ closed under reverse operation?

for a language $L$ we define $rev\left(L\right)=\left\{ \sigma_{n}\cdot\ldots\cdot\sigma_{1}\mid w=\sigma_{1}\cdot\ldots\cdot\sigma_{n}\in L\right\} $. My question is, are $\mathsf{L,NL}$ closed under ...
Ariel Yael's user avatar
1 vote
0 answers
25 views

Reduction from $\mathsf{ALL}_{\mathsf{TM}}$ to it's complement

I'd like to know if there's a reduction $\mathsf{ALL}_{\mathsf{TM}}\leq_{m}\overline{\mathsf{ALL}_{\mathsf{TM}}}$ where of course $\mathsf{ALL}_{\mathsf{TM}}=\left\{ \left\langle M\right\rangle \mid\...
Ariel Yael's user avatar
2 votes
0 answers
49 views

Proving the language 2-SIMPLE-PATH is in NL

The Question I define the language$$\mathsf{2-SIMPLE-PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c} \mathsf{there\;are\;two\;different}\\ \mathsf{simple\;paths\;from}\;s\;\...
snatchysquid's user avatar
0 votes
0 answers
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 ...
Mgh's user avatar
  • 1
0 votes
1 answer
175 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 ...
Soroush Vahidi's user avatar

1
2 3 4 5
26