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,263
questions
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 $\...
- 101
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 ...
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 (...
- 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 ...
- 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'...
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 ...
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. ...
- 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 ...
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 ...
- 1
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 ...
user163952
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 ...
- 31
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} = \...
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{...
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\...
- 133
-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 ...
- 1
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 ...
- 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 ...
-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.
- 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 ...
- 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$" ...
- 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 ...
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 ...
- 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 ...
- 1
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 \...
- 27
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 ...
- 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 ...
-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 ...
- 1
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 ...
- 327
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,...
- 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}$) ...
- 31
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 ...
- 413
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?
- 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 $...
- 305
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 ...
- 327
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 ...
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 ...
- 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 ...
- 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 ...
- 213
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 ...
- 213
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 $...
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^*$?
- 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 ...
- 13
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 ...
- 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 \...
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 ...
- 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 ...
- 141
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\...
- 141
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\;\...
- 145
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 ...
- 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 ...
