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].
955
questions
0
votes
0answers
9 views
Why can the construction of a polynomial-sized structure be done in logspace?
In paper http://www.iro.umontreal.ca/~mckenzie/Recherche/homc10fun.pdf the authors prove their problem is NL-complete. At some point in their proof however, they construct a polynomial-sized graph, ...
2
votes
1answer
76 views
Hardness of a scheduling/assignment problem
I am trying to prove the hardness of the following problem. This problem is from google hashcode, qualification-round, 2020.
Hier is a brief description of the problem. Given a list or libraries and ...
0
votes
2answers
77 views
IS there a consensus on the definition of a computer program in CS literature and if so, what is it?
The following is what I came up with from my synthetic prior research but I might be wrong.
I understand it is possible to reduce any computer "program", in a maximal reduction(?), to these features:
...
4
votes
1answer
57 views
Two versions of Subset Sum Problem
I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is:
Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w_i$, ...
0
votes
1answer
16 views
Reducing vertex cover to minimal vertex cover
What is a quick and a elegant way to reduce vertex cover to minimal vertex cover?
Is it possible to use vertex cover as verifier in the algorithm that reduces vertex cover to minimal vertex cover? ...
1
vote
1answer
32 views
Reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} $
How to reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} =\{\langle M,w \rangle: M$ is a Turing machine that accepts $w$}.
My try:
Construct a ...
4
votes
1answer
53 views
why does $ A≤_p \#SAT$ if $A \in BPP$
hello and thank you for helping me understand the following:
I really don't understand this, why if language $A \in BPP$ then $A≤_P\#SAT$?
language A is in BPP class, if for a probabilistic turing ...
3
votes
1answer
95 views
Polynomial-time linear-reduction from Directed Hamiltonian Path Problem to 3SAT
Is there a polynomial-time reduction from Directed Hamiltonian Path Problem to 3SAT which is linear in the number of vertices? That is, it reduces every directed graph $G$ with $n$ vertices to a ...
-1
votes
0answers
21 views
Creating language $L_1$ with given parameter
Suppose $G$ is a context-free grammar, the language $L_0⊆\Sigma^*$ is also context-free but not-regular and $\#\not\in \Sigma$. Using $L_{(G)}$, $\#$, $L_0$, and $\Sigma^*$ create language $L_1$ such ...
0
votes
1answer
30 views
Is L decidable or not
Let $L = \{\lt M\gt | M$ is a $TM, L(M) = \{1^n0^n | n\ge0\}\}$.
Create a reduction from $A_{TM}$ (acceptance problem) to $L$. Is $L$ not decidable?
But isn't $L$ decidable since it is possible to ...
2
votes
1answer
59 views
Is the following fuction computable?
I'm trying to show that $K_1 \le_1 K$ where $K$ is the diagonal halting set $\{x : \varphi_x(x) \downarrow\}$ and $K_1=\{x: \exists y \,\, \varphi_x(y) \downarrow\}$, then I defined the function
$$\...
1
vote
2answers
47 views
Is the number of NP-complete problems finite?
It should be straight forward to show that there are infinitely many NP-hard problems:
Proof:
Take the problem Remove 1 Vertex 3-COL ($R1V3COL$) which takes a graph $G=(V,E)$ as an instance and ...
0
votes
0answers
33 views
is L not decidable? [closed]
Let $L = \{\lt M\gt | M$ is a $TM, L(M) = \{1^n0^n | n\ge0\}\}$.
Create a reduction from $A_{TM}$ (acceptance problem) to $L$. Is $L$ not decidable?
But isn't $L$ decidable since it is possible to ...
-1
votes
1answer
25 views
if there is no reduction from A to B
I'm facing the following question :
If there is no $𝐴\leq_𝑚𝐵$ reduction,
does this necessarily mean that A is not decidable?
for any choice of B.
thanks in advance.
2
votes
1answer
51 views
Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?
Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k)
polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a ...
0
votes
1answer
38 views
What is the result of a reduction operation called?
Is there a commonly used term for the result of a reduction operation?
"reductant" does not quite sound right...
0
votes
0answers
17 views
Proof by reduction that the Universal Language is not recursive using the complement of the Diagonalization language
I have the following proof which I don't fully understand.
L D/ is the complement of the Diagonalizaton Language.
L U is the Universal language.
Assume U* is a TM for Lu which always halts. ...
0
votes
0answers
22 views
From 2IN3SAT to NAE3SAT ( not all equal )
We know that 1IN3SAT is np-complete , I will define an ne form of the SAT problem 2IN3SAT (exactly two true variables ).
2IN3SAT is np-complete because (x,y,z) is in 1IN3SAT iff (!x,!y,!z) is in ...
3
votes
1answer
162 views
Undecidability of two Turing machines acting the same way on an input
So I need to find a reduction to the (undecidable) problem of deciding if two Turing machines $M_1$ and $M_2$ behave the same way on an input $x$. "Behaving the same way" is defined like this:
$M_1$ ...
0
votes
1answer
27 views
In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects?
Let HALT be the language $\{\langle M, w\rangle : M\text{ is a TM that halts on }w \}$. Let ALLHALT be the language $\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\}$. Use a reduction ...
0
votes
0answers
24 views
reduction: L1’s decidability is unknown and L2 is undecidable
About this question:
Reductions can be tricky to get the hang of, and you want to avoid “going the
wrong way” with them. In which of these scenarios does L1 ≤m L2 provide useful information (and ...
1
vote
0answers
20 views
Proving Problems are Undecidable/ Semi decidable? E.g. Halting Problem, Membership Problem? [duplicate]
I am having issues finding similarities in different cases where a problem such as the Halting Problem or the Accept-Λ problem is reduced to the Membership problem to prove that it is semi-decidable ...
0
votes
0answers
19 views
Polynomial reduction proprietries: reflexive, transitive, but not symmetric
From theory I know the polynomial reduction is:
reflexive $A ≤ A$ (A Language)
transitive $A ≤ B$ and $ B ≤ C$, then $A ≤ C$ (A, B, and C Languages).
What about symmetric? There is an example with ...
1
vote
0answers
34 views
Complexity problem reduction?
Let say A and B are two decesion problems where A $\le$ B polinomial reduction is true.
Is this : A̅ $\le$ B̅ also true?
If so, can you show an exemple, if not why?
1
vote
1answer
29 views
Can polynomial many-to-one reduction be done to a specific problem instance?
Let's say I reduce the problem $A \in L$ to $B \in K$ , with a function $f: \Sigma^{*} \rightarrow \Gamma^{*}$ such that $w \in L \Leftrightarrow f(w) \in K$ . I know if I want to solve $A$, given ...
0
votes
1answer
77 views
NP-completeness for integer linear program
This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come ...
1
vote
0answers
45 views
PSPACE-hardness of the unbounded puzzle
Given a board of size $n \times 1$ where $n=\infty$ (basically a tape, one way infinite), and a set of colors $C$, some starting color $c_{start} \in C$, a set of templates $T$ in a form $(c_k, i, c_i,...
1
vote
2answers
55 views
Prove the Droid Trader Problem is NP-complete
This question is from chapter 8, exercise 35, of Algorithm Design by Kleinberg and Tardos.
A player in the game controls a spaceship and is trying to make money
buying and selling droids on ...
1
vote
1answer
150 views
Proving NP-Complete problem by reduction of subset-sum
My assignment question as "given a multiset of symbols (letters) L from an alphabet Σ (thus, the same letter may appear in L multiple times), and a set of words W ⊆ Σ' , UseAllLetters asks if it is ...
1
vote
0answers
23 views
Show that SQUARED-SUM-PARTITION is NP-complete
Consider the following problem SQUARED-SUM-PARTITION. You are given positive integers $x_1, \dots, x_n$,
and numbers $k$ and $B$. You want to know whether it is possible to partition the numbers $\{ ...
1
vote
1answer
112 views
How do I reduce subset sum to another problem in NP?
I'm trying to solve the following problem about arranging pens on rows. The problem goes as the following.
Given $n$ integers $l_1, \dots l_n$, the lengths of the pens, r rows and a goal G. Is it ...
1
vote
1answer
39 views
Hamiltonian cycle, verifying and finding
If we have an algorithm that in polynomial time says if a graph G has an hamiltonian cycle, can we have an algorithm that in polynomial time find an hamiltonian cycle?
My attempt is to delete an edge ...
0
votes
0answers
32 views
Reducing universal language to language of palindromes
I am trying to understand proof for proving language of all palindromes is undecidable from these slides. It tried to reduce universal language to language of all palindromes on alphabet.
The two ...
1
vote
0answers
11 views
Decide if Turing machine's language contains either a or b string
during school exercises we worked on decidability problems and there was one I don't really understand. We were provided with solution and explanation regarding this exercise but still I need more ...
0
votes
1answer
137 views
Reduction from Vertex Cover to Dominating Set
I am trying to reduce the vertex cover (decision) problem to the dominating set (decision) problem in order to prove that the latter is NP-hard. After some research online, I found that many articles ...
2
votes
3answers
83 views
Are there any problems that reduce to the halting problem?
I'm reading through sipser and there is a lot of computability problems that the halting problem reduces to, i.e. if $A_{TM} = \{\langle M,w\rangle : M$ accepts input $w\}$ then $A_{TM} \leq P$ where ...
2
votes
1answer
134 views
Example of two undecidable languages that cannot be reduced to each other
I want to find two undecidable languages $A$ and $B$ that $A$ cannot reduce to $B$, $B$ cannot reduce to $A$(Many-one reduce). One of my thought is to let $A$ be the halting problem, let $B$ be some ...
4
votes
2answers
58 views
Given a set, partition it into ordered triples
I have a set $S$ of $3m$ positive numbers $\{a_1,a_2,\ldots,a_{3m}\}$.
The question is: can you select $m$ disjoint triples $(a_i,a_j,a_k)$ from $S$ such that $a_i-a_j-a_k\geq1$?
I was trying to ...
1
vote
3answers
49 views
How do we construct reductions for NP-Completeness
I'm wondering in what direction we construct reductions to prove that a problem is NP-complete. Say the question is asking to prove that the vertex cover problem is NP-complete given that the ...
0
votes
0answers
33 views
Why does such reductions work [duplicate]
In class we saw examples of reductions like from Independent Set (IS) to Longest common subsequence (arbitrary number of sequences) (LCS)
$V = \{v_1,\ldots,v_n\} E =\{ e_1,\ldots, e_m \}$
The ...
5
votes
1answer
120 views
Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete?
I have a graph with at most two outgoing arcs for each node and I need to extract a DAG by removing the least number of arcs. I know that the general problem is np-complete but i can't reduce it to ...
1
vote
1answer
28 views
Reductions from non decision problems
I want to show a minimization problem $Y$ has no approximation factor of 1.36. To be more specific the problem $Y$ is the exemplar distance problem between two genomes. Could I reduce from the min ...
2
votes
1answer
60 views
Partition into pairs with minimum absolute difference, NP-hard?
I have a set $S$ of an even number of positive elements $2m$ and $m$ values $t_1,t_2,\ldots,t_m$ where each $t_i\leq1$ for all $i$.
The question is: can you select $m$ disjoint pairs $(a_i,b_i)$ from ...
3
votes
1answer
66 views
Can current quantum computers decide languages that Turing Machines cannot?
I am currently learning Computing Theory at university, and we were on the topic of Turing-Decidability, Recognizability, etc. Showing that a problem is undecidable with Turing machines due to ...
1
vote
0answers
36 views
How do I go about creating a mapping reduction?
So I understand what a mapping reduction is and how to create them for simpler problems such as a reduction from the set of even numbers to set of odd numbers however, seemingly more complicated ...
1
vote
0answers
57 views
Reduce duplicate subset sum problem to distinct subset sum problem?
In duplicate subset sum problem (DuSSP), we are given a multiset $\{a_1,a_2,\ldots,a_n\}$ where some of the $a_i$ are duplicates. We can assume that $a_1\leq a_2\leq \cdots\leq a_m.$ We are also given ...
2
votes
2answers
55 views
Clique-or-almost reduction to clique
I saw the posted question here about a direct reduction from near-clique to clique.
Clique-or-almost is like near-clique but with the option for a complete clique of size $k$, I mean that perhaps an ...
1
vote
0answers
16 views
What are the requirements for a superset of P to be closed under karp reductions?
So today in our exercise session on complexity theory we discussed that P, NP, and BPP are closed under karp reduction. We also figured that the proofs could likely be expanded to straight ...
0
votes
0answers
16 views
How can I convert this graph into CNF to solve the hamiltonian path with SAT?
So I have this graph,
I am following the rules outlined in these slides: https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20111018.pdf
The rules for converting the graph to CNF and the proof are in ...
1
vote
1answer
24 views
If $Q$ reduces to $L$ then $\overline{Q}$ reduces to $\overline{L}$
The following exercise is taken from Chapter 17 of Languages and Machines by Thomas Sudkamp:
Let $Q$ be a language reducible to a language $L$ in polynomial time. Prove that $\overline{Q}$ is ...
