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
5
votes
1answer
111 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
60 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
48 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
28 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
38 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 $\...
1
vote
1answer
46 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 \stackrel{+}{\...
1
vote
1answer
54 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
167 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
106 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
115 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
364 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
222 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?
3
votes
1answer
179 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 ...
3
votes
1answer
2k views

reduction from 3-SAT to Subset Sum problem

How to reduce 3-SAT to subset sum problem?
0
votes
0answers
242 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
84 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
37 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
64 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 ...
0
votes
0answers
42 views

Is reduction from A_TM to EQ_TM possible to prove EQ_TM is undecidable?

\begin{align} EQ_{\mathrm{TM}} &= {\{ \langle M,N\rangle : L(M)=L(N) \}}\\ A_{\mathrm{TM}} &= {\{ \langle M,w\rangle : \textrm{TM $M$ accepts $w$}\}} \end{align} I can do it using $E_{\mathrm{...
0
votes
0answers
61 views

Mapping reduction for the useless state problem to prove that its undecidable

I want to give a mapping reduction (many-to-one) using the Empty_TM which accepts nothing, so the accept state is a useless state. This is to show that useless_TM is undecidable. A state q in a TM M ...
3
votes
2answers
135 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
234 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
61 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
114 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
105 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
274 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
121 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
271 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
25 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
62 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
40 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
105 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
62 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 ...
23
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
90 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
21 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
758 views

Condensed Nearest Neighbor Explanation

I have a question regarding the Condensed Nearest Neighbor algorithm from ...
-2
votes
1answer
432 views

Prove PSPACE is closed under union?

How would you prove PSPACE is closed under union? So far, my thought process is that we can create an algorithm to show that P is closed under union. I'm struggling with how I can connect that to ...
-2
votes
1answer
554 views

Prove PSPACE is closed under complement? [duplicate]

How would you prove PSPACE is closed under complement? So far, my thought process is that we can create an algorithm to show that P is closed under complement. I'm struggling with how I can connect ...
-3
votes
1answer
43 views

Exponential amount of information in polynomial size? Impossible!

I'm reading A note on succinct representations of graphs by Papadimitriou and Yannakakis. Let me quote the following paragraph on page 183: Formula $F$ has a highly regular structure. It has $|x|$ ...
2
votes
1answer
108 views

Prove the languages |L<M>| = 2 and |L<M>| $\not=$ 2 to be non-Turing recognizable or non-recursively enumerable

I am trying to prove the non-recursively enumerable property of two languages. $L_2 = \{\langle M \rangle: |L\langle M \rangle| = 2\}$ and $L_{\not=2} = \{\langle M \rangle: |L\langle M \rangle| \not=...
0
votes
0answers
44 views

Reduction of complement from complexity class co-np and p

Let P $ \neq $ NP. D is in the complexity class co-NP. B is in the complexity class P. Let $ \bar{D} $ be the complement of D, then $\bar{D} $ $\leq _ {p} $ B. Is this statement true or false? My ...
2
votes
1answer
146 views

Reducing the vertex cover problem to a variation of the vertex cover problem [duplicate]

The following variation on the vertex cover problem was given: Given is an instance of graph $G = (V, E)$. Does $G$ have a vertex cover of size at most $\frac{|V|}{4}$? I was asked to prove that ...
1
vote
1answer
127 views

Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology?

Is the following true or false? Why? Let $Y$ denote the complement of the tautology problem. If a problem X is NP-hard, then there is a polynomial-time (many-one) reduction of $Y \leq_{p} X$.
1
vote
1answer
47 views

Proof of undecideability that one state is reached before another

I'm trying to show that, for a deterministic Turing machine $M=(Q,\Gamma,\Sigma,\delta,q_0)$, the language $K$, which includes all of the words $w \in \Sigma^\ast$ where the calculation of $M$ on $w$ ...
1
vote
2answers
51 views

Multivariate polynomials

Given a Diophantine equation $p(x_1,x_2,...,x_n)$, Can I find a reduction from $\text{dioph}(\mathbb{N}) \leq \text{dioph}(\mathbb{N}_e)$? $\mathbb{N}_e$ is the set of even numbers. So I have to ...
1
vote
0answers
18 views

What if SAT Turing-reduces to a problem? [duplicate]

To show that problem is NP-hard, we take a known NP-hard problem and reduce it to the problem whose NP-hardness we want to prove. The reduction we need is polynomial time reduction. But If I take ...
0
votes
1answer
287 views

Showing party invitation problem is np-complete

Suppose you and your $k - 1$ housemates decide to throw a party. Each housemate $i$ gives you a list $P_i$ of people she would like to have invited to the party. Depending on how much you like ...
1
vote
1answer
47 views

Is there any problem that is R-complete and RE-complete

R-complete, i.e. it is an analogue to all recursive language can be reduced to that problem and also recursive? Or is there a really such definition? RE-complete is described on wikipedia. But what ...
1
vote
1answer
175 views

Show Resource Allocation Problem is NP-Complete

We are given $n$ tasks and $m$ resources. Each task $i$ requires a set $S_i$ of resources to be active, and each resource can be used by at most one task. The Resource Allocation problem asks: given $...

1 2 3 4 5 20