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].
930
questions
1
vote
1answer
31 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
13 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
107 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
34 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
24 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
10 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
52 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
2answers
38 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} = \{<M,w> : M$ accepts input $w\}$ then $A_{TM} \leq P$ where P is ...
2
votes
1answer
91 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 ...
3
votes
1answer
42 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
41 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
32 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
95 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
25 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
56 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
52 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
34 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
41 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
47 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
14 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
15 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
23 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 ...
3
votes
0answers
65 views
LogSpace reductions vs. PTime reductons for defining PSpace-completeness [closed]
Continuing Is every PSPACE-complete problem complete with respect to logspace reductions? : earlier, PSPACE-completeness was defined via logspace reductions (e.g., cf. http://www.cs.cornell.edu/~kozen/...
1
vote
1answer
73 views
How to encode reachability in a graph with walls as a SAT problem
Suppose we have a graph that represents a grid of cells. We are given a cell to start in and a cell that's the destination. There are cells that we cannot enter and they are known as walls. Finally we ...
0
votes
0answers
47 views
Deciding whether $f(x) = f(y)$ is beyond RE and coRE
I would like to prove that the following subset is outside both RE and coRE:
$$A = \{ (p, (d_1, d_2,\dots, d_k)) \mid \text{for each } 1 \le i,j \le k, \; [p]d_i = [p]d_j \}, $$
where $p$ is a ...
1
vote
1answer
43 views
Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?
NL-Complete languages are defined by Log-space reduction, while PSPACE complete languages are defined by poly-time many-to-one reduction.
According to these posts :
Why not polynomial-space ...
2
votes
0answers
21 views
Concurrent Element-wise Reduction Algorithm (multi-threaded) (C++)
I'd like to implement a high-performance implementation of a multi-threaded reduction, element-wise, on x86 CPUs. Without loss of generality, assume the reduction operation is a sum of integers (so, ...
1
vote
1answer
107 views
Is Finding A Hitting Set of Size n/2 NP-Hard?
In Hitting Set problem we are given a collection E of subsets of V and we want to find smallest subset H of V which intersects (hits) every set in E.
In decision version of the problem, we are asked ...
1
vote
1answer
88 views
Concrete example of Vertex Cover to Subset Sum reduction
In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem, mostly to prove Subset Sum is NP-Complete. I also see a reduction in the line ...
0
votes
1answer
36 views
I want to know where there is the flaw in my argument
I came across following problem to finding whether the following language is decidable or semi-decidable or not even a semi-decidable.
$L: \{\langle M\rangle: M\space is\space a\space TM\space and\...
2
votes
2answers
118 views
How to prove NP-hardness from scratch?
I am working on a problem of whose complexity is unknown.
By the nature of the problem, I cannot use long edges as I please, so 3SAT and variants are almost impossible to use.
Finally, I have decided ...
0
votes
0answers
33 views
If two languages are reducible to the same third language, are they necessarily reducible to one another?
Speaking of polynomial time reductions.
1
vote
0answers
136 views
Proof by reduction and Turing machines [closed]
This is a practice question I have, but I can't wrap my head around it.
.............
Let L = {M | M is a TM that halts with exactly two words on its tape in the form Bw1Bw2B}.
B = Blank Position
the ...
2
votes
1answer
32 views
Can't find a mistake in reduction from RE language to a non-RE language
In the book Introduction to Automata Theory there is a question 9.3.4 that asks if a question "whether a language L(M) is infinite" is RE or non-RE? I've seen the answer, that its non-RE, however I ...
0
votes
1answer
48 views
Variant of TSP: allow each vertex to be visited at most twice
We are given a finite set $V$ and a set of distance $d : V\times V \rightarrow R\ge 0$ and we wish to compute a tour. Suppose we allow each vertex to be visited at most twice in the tour. How can we ...
1
vote
2answers
121 views
Is finding a minimal set of seed variables for a complete deduction of a system of equations NP-complete?
Suppose we have a set of variables $V$. We also have a set of equations $E$, which are sets of at least two variables. We don't know anything about these equations, except if we know all but one of ...
2
votes
1answer
499 views
Halting problem in EXP-complete
I have some troubles understanding why the halting problem is in EXP.
In Wikipedia the following is written:
It is in EXPTIME because a trivial simulation requires O(k) time, and the input k is ...
0
votes
1answer
54 views
A doubt on converting NOT gate to CNF formula
For a NOT gate if $x_1$ is input and $x_2$ is the corresponding output, I see the equivalent CNF (conjunctive normal form) is $(x_1 \lor x_2) \land (\overline x_1 \lor \overline x_2)$.
My ...
1
vote
1answer
29 views
Differences between ALLTM and INF
The definitions of ALLTM and INF are as follows:
$$\mathrm{ALLTM} = \{ \langle M \rangle \mid \text{ TM $M$ such that $L(M) = \Sigma^*$} \}. $$
$$\mathrm{INF} = \{ \langle M \rangle \mid \text{...
0
votes
1answer
60 views
Is every Turing complete set for EXPSPACE autoreducible?
I'm reading about autoreducibility, which is the following notion:
A set $L$ is autoreducible
if there is a polynomial-time oracle Turing machine $M$
that accepts $L$ using $L$ as an oracle, ...
0
votes
3answers
88 views
How Reduction works in proving NP-Hard?
A problem $X$ is $NP$-Hard if for all $Y \in NP$, $Y \leq_P X$. Further, if a problem $Z$ is $NP$-Complete, and $Z \leq_P X$, then I can prove (rather mechanically) that $X$ is $NP$-Hard.
I also ...
1
vote
1answer
40 views
Why is $ZPP \geq BPP$ not true?
This seems like a silly question, but I couldn't find a conclusive answer for it.
As far as I know, ZPP contains algorithms which run in polynomial time and either return a known-correct answer or ...
1
vote
1answer
30 views
Prove that there is no computability reduction HP $\le$ $\Sigma$*
I tried to prove in negative way that there is computability reduction HP $\le$ $\Sigma$* and accept contradiction because of HP $\in$ RE and $\Sigma$* $\in$ R but it feels that is not strong ...
1
vote
2answers
89 views
Reduce subset sum to 3SAT
How to do it?
I'm not asking the solution for the proof of why subset sum is NPC, but rather the opposite reduction
5
votes
1answer
62 views
NP-hardness even with perturbations
Consider the following problem, which can be called "2-SET-PARTITION":
Given two sets of positive numbers, $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$, where $\sum_{i\in[n]}a_i = \sum_{i\in[n]}b_i = 2 S$,...
4
votes
1answer
34 views
Normal colorings of cubic graphs to SAT
This problem is related to ”Normal coloring of cubic graphs (part 1) - a previous post. We repeat the definitions, slightly modified so as to get to the point (we define normal edge 5 colorability, ...
0
votes
1answer
55 views
Is function `number of TM which terminates on an empty word` computable?
Let f: N → N be a function where ...
3
votes
0answers
72 views
Proving NP-completeness of an extension in List Coloring Problem
In the List Coloring Problem (LCP), one is given an undirected graph $G(V,E)$, each vertex $v \in V$ is given a list
of permissible colors $L(v) \subseteq \{1,2,\dots,k\}$, we want to find a coloring $...
1
vote
1answer
43 views
Reduction to proof undecidability of the problem: machine M and N accept infinitely many words
I am struggling with the following problem:
Decide whether this problem is decidable or not: For two given Turing Machines M and N, there exists infinitely many words accepted by both machine M and ...
2
votes
1answer
69 views
How to prove the language of Turing machines that run at most $4|x|^2$ steps is not recursive?
I am trying to prove that the language
$$ L=\{M\mid M\text{ is a TM and for all }x\in \Sigma^*\text{ with }|x|>2, M\text{ on }x\text{ runs at most }4|x|^2\text{ steps}\} $$
belongs to Co-RE but ...
