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
3
votes
0answers
611 views

Minimum clique cover

How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time? Having an undirected graph, I am trying to partition all its ...
0
votes
1answer
200 views

pseudo-polynomial reduction from 3-Partition to Partition

A problem $\Pi'$ is pseudo-polynomially reducible to the problem $\Pi$ ($\Pi' \leq_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in pseudo-polynomially ...
1
vote
0answers
28 views

Example of a Karp reduction between problems in NP that is not a Levin reduction?

What is an example of a Karp reduction $f$ between two problems $A, B$ in $\textbf{NP}$ such that $f$ does not provide a way to transform certificates of one problem into certificates of the other? In ...
3
votes
1answer
431 views

Showing Maximum Independent Set is $NP-hard$

I've read about Maximum Independent Set problem being both $NP-hard$ and $CoNP-hard$. I know this can be shown using reduction from the corresponding Max-Clique problem, But I'm wondering - Is that ...
2
votes
1answer
44 views

NL-Hardness of Target

When revising for an upcoming exam in complexity theory, I came across this problem on the final part of a question, which I was unable to solve: $ TARGET = \{<G, t> : t\ is\ reachable\ from\ ...
2
votes
1answer
146 views

Can these two languages be reduced to one another?

Given: $L_1=\left\{ \left\langle M\right\rangle :L\left(M\right)\ni w_{0}\right\}$ $L_2=\left\{ \left\langle M\right\rangle :L\left(M\right)=\left\{ w_{0}\right\} \right\}$ I believe I've managed ...
2
votes
1answer
75 views

Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?

We say that two languages $L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $f:\Sigma^*\to\Sigma^* $ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^*$ ...
1
vote
1answer
141 views

Reduction from NP-complete problem to unknown complexity problem and vice-versa

Suppose I have two problems: $B$, which is NP-complete, and $A$, of unknown complexity. Question: If I show that $B \le A$ I can state that $A$ is also NP-complete because the two required ...
2
votes
1answer
65 views

How to reduce EQU to UNI?

Let $$\texttt{EQU}=\{u\#v \mid T(M_u)=T(M_v)\} \\ \texttt{UNI}=\{w \mid T(M_w)= \Sigma^*\}$$ How can you prove $\texttt{EQU} \leq \texttt{UNI}$? The idea I have so far is, to simulate the TM that ...
3
votes
1answer
92 views

How to reduce $\{w \mid |T(M_w)| \geq 42\}$ to the halting problem?

For a string $w$, $M_w$ denotes the Turing machine whose encoding is $w$. I want to reduce the language $L=\{w \mid |T(M_w)| \geq 42\}$ to $H_0 = \{w \mid M_w \text{ halts on } \epsilon\}$, but I ...
2
votes
0answers
79 views

NP-completeness of Induced disjoint paths between a set of sources and a set of sinks

In a given undirected graph $G(V,E)$, a set of $k$ paths is said to be induced if: They are vertex-disjoint. Each one is itself an induced path. No edge connects two vertices of two different paths. ...
-1
votes
1answer
34 views

If a problem C is NP hard and there is an existing reduction from/to A,B,D, are they NP hard as well?

Lets say there is an reduction in polynomial time from problem A to B, from problem B to C and from problem C to D. Now lets say C is NP hard. Does this mean A,B,D are NP hard as well?
2
votes
2answers
67 views

Turing machine reduction task

I am having trouble solving the following task: Given is the language $$D=\{ \langle M, w \rangle \mid \text{$M$ is a Turing machine and $M$ enters all states on input $w$}\}$$ Prove that $D$ ...
1
vote
3answers
666 views

How to solve the optimization of bin packing using the decision version

Let us say the optimization version of the bin packing problem asks you to give a packing using the fewest bins possible and the decision version asks if it is possible to pack the bins into $k$ bins. ...
0
votes
0answers
33 views

Two (oracle) turing machines producing the same language

I need to solve the question if two given oracle turing machines M$_{1}$ and M$_{2}$ have the same language, so T(M$_{1}$) = T(M$_{1}$). An oracle turing machine can use such an oracle for deciding ...
5
votes
1answer
229 views

Reduction from Exact Cover to Fixed Exact Cover

I am trying to reduce Exact Cover to Fixed Exact Cover to show that Fixed Exact Cover is NP-Hard. Exact Cover Input S = {x1, x2, ..., xn} (set) P = {P1, P2, ..., Pm} (subsets of S) Decision ...
1
vote
1answer
87 views

Parity Hamiltonian path problem

Wikipedia says that Hamiltonian path problem is NPC, but Parity Hamiltonian path problem (i.e., is there an odd amount of hamiltonian path) is P. Does a reduction from, e.g., SAT, to HPP, unavoidably ...
1
vote
1answer
111 views

Prove disprove an existence of mapping reduction between 2 sets

I am currently studying mapping reduction in computational theory and finding it hard to grasp the concept fully. For reference, consider the following given WHILE-Prog sets: A = { (p.d) | p doesn'...
0
votes
1answer
48 views

Is $L=\{\langle M\rangle\mid L(M)\subseteq HP\}\in coRE$?

My intuition is that $L\notin coRE$, but I haven't managed to prove that $HP \le L$, as previously I only saw reductions from $HP$ or from $\overline{HP}$ with $f$ such that $f((\langle M\rangle,x))=\...
1
vote
1answer
43 views

If a problem Q is NP complete, is another problem reducible to Q also NP complete?

Let's say $\mathcal{P}$ is a yes/no prolem with an existing reduction to the problem $\mathcal{Q}$ (with time complexity $\mathcal{O}(n^2)$). $\mathcal{Q}$ is NP complete. Does this mean that $\...
2
votes
1answer
61 views

If well-founded induction holds, then the relation $\to$ on a reduction system terminates

I am trying to understand a proof from "Term Rewriting and All That" by Baader and Nipkow. Well-founded induction (WFI) is the following statement: $\forall x \in A(\forall y \in A(x \...
1
vote
1answer
55 views

Proving that the set of grammars generating L or L complement is undecidable

Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
5
votes
1answer
185 views

Prove that “Finishing the degree in three years” problem is NP-Complete

I was asked in an interview the following question: We'll define the "Finishing the degree in three years" problem in the following manner: Given a list of courses $C=\{c_1, c_2,\ldots, c_n\}$, ...
2
votes
3answers
353 views

If P = NP, does SAT, or any other NP-Complete poly-reduce to any language different from $\emptyset$ or $\Sigma^*$?

I looked at Sipser ("Introduction to the Theory of Computation"), Problem 7.17: Prove that if P = NP, then every language in P, except $\emptyset$ and $\Sigma^*$, is NP-Complete. The solution is ...
2
votes
1answer
152 views

Proving NP hardness in Puzzle with SAT reduction

Introduction I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The algorithm follows an infinite language based on ...
2
votes
1answer
1k views

Is maximum-leaves spanning tree np-complete?

How can we show that a maximum-leaves spanning tree is NP-complete? what other np-complete problem we can use as our reduction base? (maximum-leaves spanning tree: does G have a spanning tree with at ...
1
vote
1answer
298 views

for two languages in $NP$ does one of them karp reducible to another?

$\forall A, B \in NP \implies A<_m^{poly}B. \lor B<_m^{poly} A.$ I want to know is there any work around this theorem? or is it correct?
4
votes
1answer
369 views

Why is Graph Isomorphism downward self reducible?

To say that graph isomorphism is downward self reducible means the following: There is an algorithm which decided graph isomorhpism for two given graphs of n vertices in polynomial time by accessing ...
4
votes
1answer
5k views

reduction from 3-SAT to Subset Sum problem

How to reduce 3-SAT to subset sum problem?
0
votes
0answers
346 views

How can I reduce Subset Sum to Almost Subset Sum?

Maybe this is quite simple, but I am having some trouble how to do this reduction. I want to reduce Subset Sum to Almost Subset Sum. Subset Sum: given a set of positive integers $A=\{a_1,a_2, \dots,...
0
votes
2answers
136 views

Assume we have an algorithm HC for HAMILTONIAN CIRCUIT. How is it possible to convert the HC algorithm to an algorithm HP for HAMILTONIAN PATH?

My understanding is that I have to use the algorithm for Hamiltonian Circuit to help solve the Hamiltonian Path problem. My understanding is that we have to perform a reduction from Hamiltonian Path-...
1
vote
0answers
46 views

Finding weakly-negative cycles

In a directed graph where the edges may have positive or negative weights, the Bellman-Ford algorithm detects cycles in which the sum of weights is strictly negative ($<0$). I need to detect cycles ...
2
votes
2answers
141 views

Symmetry of NP completeness

To show that some problem X is NP-complete, we usually show that it is in NP and that an efficient algorithm for deciding X implies an efficient algorithm for deciding some known NP-complete problem ...
3
votes
2answers
192 views

Is the empty problem (or its complement) Karp reducible to any problem in NP?

I'm currently following a course on Complexity Theory, and whilst studying, I came across a rather counterintuitive statement: If $\textbf{P}=\textbf{NP}$, the following holds: For every $A \in \...
0
votes
0answers
367 views

How to prove coNP is closed under reverse Karp Reduction?

Is it true that $A \leq_k B \land B \in \mathsf{coNP} \implies A \in \mathsf{coNP}$? If so, how would you go about proving it?
0
votes
1answer
103 views

Finding a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$

I am trying to find a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$, but I can't seem to find one. Definitions: $$\begin{align*} CF_{TM} &= \left\{ \langle M \rangle \mid \text{$M$ is a ...
4
votes
1answer
276 views

How to prove SPACE-TMSAT is PSPACE-hard?

I understand that the language: $\operatorname{SPACE-TMSAT} = \{⟨M, w, 1^n⟩ : \text{DTM $M$ accepts $w$ in space $n$}\}$ is in PSPACE since it doesn't use more than $n$ space. But to prove that it ...
1
vote
1answer
240 views

is it possible to reduce $HALT_{TM}$ to $E_{TM}$?

I am wondering, if it is even possible: is it possible to reduce $HALT_{\text{TM}}$ to $E_{\text{TM}}$? $HALT_{\text{TM}}=\{\langle M,w\rangle\mid M\text{ is a }TM\text{ and }M\text{ halts on input }...
3
votes
1answer
452 views

Reducing Exact Cover to Subset Sum in practise!

The reduction of Exact Cover to Subset Sum has previously been discussed at this forum. What I'm interested in is the practicality of this reduction, which I will discuss in section 2 of this post. ...
1
vote
0answers
150 views

The NP completeness proof for a variation of the 3CNF-SAT problem

There is a variation of 3CNF-SAT which is called 10-3-CNF-SAT = {<$\Phi$>: $\Phi$ is a satisfiable CNF formula with $\textbf{at most}$ 3 literals per clause and every variable occurs in $\textbf{at ...
2
votes
1answer
663 views

Is this problem NP-Complete (Bin packing with seperable items and penalty)?

The problem is a bit like bin-packing, so I'll describe it with similar naming: You have $N$ bins, with the same size, $V$, where $V$ is a positive integer This problem has items, and also "pieces" ...
1
vote
1answer
35 views

Shortening the number of reductions to prove NP-Completeness

This question is based on the slides from this pdf: Slide 54, they define the Subset Sum Problem. Slide 65, they define the Partition problem. Slide 74, they talk about the Job Scheduling problem. ...
2
votes
2answers
80 views

NP-Completeness and commutative property

If $X$ is NP-complete and for some $Y, X\leq_p Y$ and $Y\leq_p X$ what can we say about $Y$? My intuition says that this is only the case when $X=Y$ but I'm not sure how to justify this.
3
votes
1answer
49 views

Constructing a reduction between two languages about pairs of Turing machines

I'm curious about a potential relation between the following two languages. $L_1 := \{\langle M_1, M_2 \rangle : L(M_1) \cap L(M_2) \ne \emptyset \}$. $L_2 := \{\langle M_1, M_2 \rangle : L(M_1) \...
1
vote
1answer
271 views

Polynomial Time reducible explanation

Have a set of examples given to me, but I'm pretty sure they're all wrong. Can someone verify that my understanding of them is correct? If set $Y$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $X ...
0
votes
0answers
178 views

Is this a valid proof for “Karp-polynomial reduction is not symmetric”?

Let $L = \emptyset$ and $L' = \{a\}$ be two languages over an arbitrary non-empty alphabet $\Sigma$, $a \in \Sigma$. $L$ can be reduced to $L'$: the reduction just transforms anything it is given ...
22
votes
2answers
5k views

If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku. Can you treat this program as a black box and use this to solve ...
3
votes
0answers
126 views

A special case of the SUBSET SUM problem

Consider the following special case of SUBSET SUM Inputs: Positive integers $a$ and $b$ with $a \ne b$, and positive integers $k$ and $t$, with $k$ specified in unary. Encoding: These inputs (...
0
votes
0answers
34 views

Cluster with categorical / ordinal

i have a dataset with movies review. I wish cluster my element but inside i have a categorical / ordinal values. i seen that exist: MCA (Multiple Correspondence Analysis) https://www.utdallas.edu/~...
0
votes
1answer
963 views

Condensed Nearest Neighbor Explanation

I have a question regarding the Condensed Nearest Neighbor algorithm from ...

1
3 4
5
6 7
22