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

954 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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'...
28 views

46 views

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-...
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 ...
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 ...
42 views

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?
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 ...
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 ...
105 views

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" ...
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. ...
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.
40 views

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 ...
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 ...
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 (...
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/~...
758 views

### Condensed Nearest Neighbor Explanation

I have a question regarding the Condensed Nearest Neighbor algorithm from ...
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 ...
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 ...
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|$ ...