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].

Filter by
Sorted by
Tagged with
0
votes
0answers
4 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
4 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
105 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
46 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
72 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
87 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
1
vote
0answers
134 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
493 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
88 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 ...