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
-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
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. ...
- 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
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 ...
- 1
0
votes
1
answer
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 ...
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
36
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
49
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
118
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
24
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
98
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
38
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
46
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
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 ...
- 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
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,...
- 25
3
votes
0
answers
55
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
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?
- 1
0
votes
2
answers
36
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
162
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
83
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
27
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
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 ...
- 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
34
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
24
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
48
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
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
1
answer
19
views
Are the indices of variables in the formula variable?
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(\...
- 2,932
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?
...
- 3
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),\...
- 161
-1
votes
1
answer
35
views
A sufficient condition for unsatisfiability
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 ...
