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,232
questions
0
votes
1
answer
54
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
19
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
31
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
0
answers
16
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
29
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
18
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
25
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
21
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
42
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
50
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
104
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
18
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,913
0
votes
0
answers
31
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
27
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
34
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 ...
0
votes
2
answers
55
views
Ιf 3SAT reduces to its complement then NP=coNP
Can you please explain to me why the following is true?
Ιf 3SAT reduces to its complement then NP=coNP.
Thoughts:
3SAT is NP-complete so for every X in NP
$X \leq 3SAT$
$\overline {3SAT} $ is NP-...
- 37
0
votes
1
answer
31
views
$L_1= (1$ { $0, 1$ }$^∗) \cup ${ $0x | x \in L$} is NP- complete
If L is NP-complete then how can I prove that $L_1$:
$L_1= (1$ { $0, 1$ }$^∗) \cup ${ $0x | x \in L$}
is also NP- complete.
My thoughts: A reduction from (for example) SAT to L can be converted to a ...
- 37
0
votes
0
answers
17
views
Beta reduction and sequence of effect
The famous Monad is well known for handling effect in a functionally pure manner (e.g. IO Monad).
On the other hand, in some application, runtime performance is the utmost interest and the compile ...
0
votes
0
answers
82
views
Reduction from Partition problem to the same problem with the input replicated multiple times
In a variant of the Partition Problem given a multiset $S = \{a_1,\dots,a_n\}$ of positive integer with the total sum $\sum_{i=1}^n a_i = m\,T$, we want to find out if exists a partition $S_1,\dots,...
- 1
0
votes
0
answers
24
views
How to prove by reduction this (acceptance?) problem
At school I was assigned this example:
Prove by the reduction method that it is undecidable whether for a given Turing machine M with the alphabet {a, b, _} holds aabb ∈ L(M).
I think it's acceptance ...
- 3
0
votes
0
answers
91
views
Reduction from LONGEST PATH to HAMILTONIAN PATH
LONGEST PATH is the decision problem asking if a simple path of at least $K$ edges exists in a graph $G$.
The reduction from ...
- 3
0
votes
1
answer
60
views
4DM is NP-complete
Is 4DM NP-complete?
An instance of 4DM consists of four disjoint sets X, Y, W and Z of size k, and a set Q of quadruples $Q = \{ (x, y, w, z) \mid x ∈ X, y ∈ Y, w ∈ W, z ∈ Z \}$
Question: Is there a ...
- 37
1
vote
1
answer
50
views
Variation of 3-SAT
I already know that SAT and 3-SAT are NP-complete.
If in 3-SAT the Boolean expression should be divided to clauses,such that every clause contains at most (in the original problem it says exactly) ...
- 37
0
votes
2
answers
47
views
Is a language semi-decidable iff it is reducible to ATM?
Thank you. I see how it makes sense going in the opposite direction but i need help proving that this is true.
Below is the definition of ATM.
ATM={<M,w>| a TM, M accepts w}
The question from my ...
- 1
-1
votes
1
answer
39
views
Showing NP-completeness of a graph problem with vertex capacities
The problem:
Given an undirected graph G = {V, E}, a source-vertex s, and each vertex having a "capacity" between 0 and |V|, is there a tree which covers all vertices and does not extend ...
0
votes
0
answers
37
views
Can the airline scheduling algorithm (network flow) be extended to handle seating capacities?
The airline scheduling problem determines the minimum number of airplanes required to service a set of passenger flights, where a plane can service routes A$\rightarrow$B and C$\rightarrow$D if there ...
-2
votes
1
answer
30
views
How to prove that it is NP-complete?
I was trying to do this exercise, but I don't know how to solve this problem is NP-complete, what reduction to do.
There is a network N of n people, in which every person i is associated with a subset ...
1
vote
1
answer
55
views
How to reduce universal language to language of all turing machines that deduce all palindromes?
Let $S$ be language $$\{\langle M\rangle \mid(\forall x \in \Sigma^*)[x \in L(M) \iff x^R \in L(M)]\}.$$
How can I show that $L_U \le_m S$ and $L_U \le_m \bar S$ where $L_U$ is universal language and $...
- 125
0
votes
0
answers
40
views
$L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$
About the language $L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$
I want to determine if it is in RE / coRE or neither.
I think that I found a mapping reduction from $\overline{A_{TM}}$ to $L$, ...
- 37
1
vote
1
answer
32
views
Reducing problems to solve easier problems
Is there any instance where a problem $A$ can be reduced to a problem $B$ where $B$ is easier to solve than $A$?
I've been learning about NP-Hardness recently and seems that the answer is no. Whenever ...
- 13
0
votes
0
answers
19
views
To Prove NP-Completeness [duplicate]
Given a Directed Graph G, and some subsets of vertices T1,T2,..Tn(These subset can intersect) , is there a path in this graph such that it is acyclic and contains exactly 3 vertices from each Ti. I'm ...
- 1
1
vote
1
answer
148
views
Show problem is NP-hard
I'm preparing for my exam and I got stuck on the following problem:
The gardening problem:
We have access to a set of different types of seeds and a number of plant pots.For each plant pot, there is ...
- 21
1
vote
1
answer
45
views
Mapping reduction - Bit Flip
Let $L=\{<M> | M$ is a TM, $L(M)\ne \emptyset$ and $\forall x\in L(M), \overline{x} \notin L(M) \}$
While $\overline{x}$ is the bit flip of $x$.
I want to show a mapping reduction to prove that ...
- 37
0
votes
2
answers
45
views
Reduction from SUBSET SUM to COIN CHANGING
The COIN-CHANGING problem is NP-complete, but I am having difficulty finding a proof for its NP-hardness in the form of a reduction from another NP-complete problem ...
- 3
1
vote
1
answer
24
views
Choosing the ideal problem to prove the hardness
I am research scholar currently working in complexity theory. Recently, i have started working on hard proofs and reductions. It is very well established that there is a polynomial reduction from ...
2
votes
1
answer
52
views
NP-hard $k$-SAT variant with exactly $\ell$ occurrences per variable
For the purpose of this post, let $k$-SAT be SAT with exactly $k$ literals per clause, as opposed to the more common meaning of at most $k$ literals per clause.
With the purpose of proving some ...
- 665
0
votes
1
answer
29
views
NP-hard (3-)SAT variant with $n$ clauses and $f(n)$ variables
With the purpose of proving my problem NP-hard, I'd like to reduce from a SAT variant (which of course should remain NP-hard) in which not two parameters are present (typically $n$ clauses and $m$ ...
- 665
0
votes
0
answers
161
views
Halting problem reduction to single digit numbers
I'm thinking of the solution for severaly days, but I'm not sure about my solution is on the correct way.
I need to prove that the next problem is undecidable:
Input: An N program which requires an y ...
1
vote
1
answer
159
views
Graph Isomorphism Problem: decisional vs functional
The Graph Isomorphism Problem is a classic in Computer Science.
In its decision version $(DGI)$, we are given two graphs $G$ and $H$ and we are asked if there exists an isomorphism between the two. In ...
- 133
0
votes
1
answer
26
views
Assume we know that (1) $A$ reduces to $B$ in time $O(f(n))$ time and (2) $B$ reduces to $A$. What can we say about the time for $B$ -> $A$?
The question is basically the title. If two NP-Complete problems reduce to each other, do we know that the reductions take equal amounts of time? What about space? Does this apply for all 'invertible' ...
- 103
0
votes
0
answers
15
views
Finite complexity meta-algorithm to generate (non-asymptotically) polynomial time shortcuts to EXPTIME problem of arbitrary input size
I might be able to find a polynomial time reduction to an EXPTIME algorithm of finite size, but is it possible for a finite-description-length algorithm to exist that finds polytime shortcuts for any ...
- 101
0
votes
0
answers
111
views
Reduce the independent set problem to the set packing problem
I got this question in my compsci homework and tried the reduction from the solution with an example and it doesn't seem to want to work.
Here's the proposed reduction:
The independent set problem ...
2
votes
1
answer
52
views
Show this 2D Grid Set Cover-ish problem is NP-Complete?
Given a $n \times m$ rectangular grid of cells each with an integral weight: $w_{i,j}$ and two integer parameters $w \ge 2$ and $h \ge 2$ (for group width and height respectively). Select the subset ...
- 313
0
votes
1
answer
39
views
show for any Languages $L_1$ and $L_2$ exists a Language $L$ with $L_1 \leq_{log} L$ and $L_2 \leq_{log} L$
This is an old exam question, but I never found a solution or somebody who could explain it to me. Here is the problem statement:
Let $\Sigma$ be an alphabet with |$\Sigma$| $\geq 2$.
Show that for ...
- 13
3
votes
0
answers
39
views
Can fine-grained hardness be proved directly from classical hardness (e.g., $\sf P \neq NP$) in some way?
I have just learnt about some typical result of fine-grained hardness in 15-455 by Prof Ryan: CNF-SETH implies ${\sf DIAMETER} \notin {\sf TIME}(mn^{1-\epsilon})$. (Here DIAMETER stands for the graph ...
- 191
1
vote
0
answers
55
views
Do all NP-Complete problems run in $O(c^n)$ time, as opposed to $O(c^{n^k})$?
According to the Wiki article on NP-Completeness, NP-Complete problems can be solved in $O(c^{n^k})$ time (I'll call this EXP-POLY time). However, shouldn't the bound on all their run times be the ...
- 502
0
votes
1
answer
28
views
Reductions but no algorithms
in "Introduction to Automata Theory, Languages and Computations" by Motwani, Ullman and Hopcroft, when they need to prove, for instance, Rice's theorem, they reduce the universal language, $...
- 1
2
votes
0
answers
30
views
Reductions from 3-SAT that won't work directly from SAT
Our prof talked about why it's good to know that 3-SAT is NP-complete because it's easier to craft reductions from it than from plain SAT.
However, all the examples we've seen (reduction to ...
- 21
1
vote
2
answers
142
views
An intuitive explanation of "provably complex combinatorial games"
It is very surprising to me that some combinatorial games such as generalized chess are EXPTIME complete. I have no idea why having a solver for a combinatorial game allows you to solve arbitrary ...
- 3,472
0
votes
0
answers
62
views
Polynomial Reduction from 3SAT
Given an undirected graph $G=(V,E)$ where $V$ is a set of vertices, and $E$ is a set of edges and
given a set $D$ where $D \subseteq V $ and $ \forall v \in V \setminus D \: \mid \: \exists w \in D : ...
- 1