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

1,284 questions
Filter by
Sorted by
Tagged with
4k views

### How to reduce to an NP-hard problem?

For an assignment I have to program an application to schedule conversations. There is an event where representatives of the elementary schools talks with the representatives of high schools. They ...
• 141
9k views

### Reduction from set cover problem to vertex cover problem

Although the reduction from vertex cover problem to set cover problem is quite simple, I did not find anywhere the reduction in the opposite direction. From the similarity in the type of problems, I ...
• 513
547 views

### Hardness of counting solutions to NP-Complete problems, assuming a type of reduction

The $\text{NP-Complete}$ class of problems is defined w.r.t Karp Reductions, which are polytime many-one reductions. However, they need not necessarily preserve the number of solutions. A more ...
1 vote
64 views

### Produce decision version of the problem

An optimisation problem requires minimising some function $f(x)$, where $x$ is a vector of integers. What is the corresponding decision version of the problem?
3k views

### Types of reductions and associated definitions of hardness

Let A be reducible to B, i.e., $A \leq B$. Hence, the Turing machine accepting $A$ has access to an oracle for $B$. Let the Turing machine accepting $A$ be $M_{A}$ and the oracle for $B$ be $O_{B}$. ...
3k views

### Reducing TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SAT

In Cormen's Algorithms book on NP-completeness they prove various problems are NP-complete by reducing a previously proved NP-complete problem (call $K$) to current problem (call $L$). Each proof ...
• 309
5k views

### How are all NP Complete problems similar?

I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps. Prove that current problem is NP, i.e., given a certificate, prove that it can be verified ...
• 309
334 views

### Can an exponential algorithm for an NPC problem be transformed into an algorithm for other NP problems in polynomial time?

After looking at other questions and my textbook, I seem to get some confusion. I do get that when there is a polynomial algorithm of NPC, there is a polynomial algorithm for a NP problem. But the ...
240 views

### Find a permutation that maximize the minimum of $\frac{a_n}{a_{n-1}} + \frac{a_n}{a_{n+1}}$

Consider a sequence of $n$ positive real numbers $a_0,\ldots,a_{n-1}$. Let $S_n$ be the set of permutations on $\{0,\ldots,n-1\}$. We are interested to find  \max_{\pi\in S_n}\left( \min_{i=0}^{n-...
• 3,083
4k views

### Optimization problem vs decision problem - reduction

Assume we have an optimization problem with function $f$ to maximize. Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
1k views

### Showing that the set of TMs which visit the starting state twice on the empty input is undecidable

I'm trying to prove that $L_1=\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q_0 \text{ at least twice on } \varepsilon\} \notin R$. I'm not sure whether to reduce the halting ...
• 511
7k views

### Is MAX-SAT NP-hard?

Is the MAX-SAT problem NP-hard? From the Wikipedia page: The MAX-SAT problem is NP-hard, since its solution easily leads to the solution of the boolean satisfiability problem, which is NP-complete ...
2k views

### A polynomial reduction from any NP-complete problem to bounded PCP

Text books everywhere assume that the Bounded Post Correspondence Problem is NP-complete (no more than $N$ indexes allowed with repetitions). However, nowhere is one shown a simple (as in, something ...
• 193
382 views

### What complexity class does this variation of traveling salesman problem belong to?

Given a TSP instance $T$, decide whether changing the city coordinates by adding a vector of coordinates $v$ will change the optimal TSP objective by atleast $x$. The city coordinates are integers. ...
• 61
1k views

### Is SAT in P if there are exponentially many clauses in the number of variables?

I define a long CNF to contain at least $2^\frac{n}{2}$ clauses, where $n$ is the number of its variables. Let $\text{Long-SAT}=\{\phi: \phi$ is a satisfiable long CNF formula$\}$. I'd like to know ...
• 472
3k views

### Is Karp Reduction identical to Levin Reduction

Definition: Karp Reduction A language $A$ is Karp reducible to a language $B$ if there is a polynomial-time computable function $f:\{0,1\}^*\rightarrow\{0,1\}^*$ such that for every $x$, $x\in A$ if ...
• 503
299 views

### The $\text{k-key}$ problem

Given an undirected graph, I define a structure called k-key as a path containing $k$ vertices which are connected to a simple cycle which contains $k$ vertices as well. Here's the k-key problem: ...
• 103
297 views

### Does a collision oracle for the pigeonhole subset sum problem produce solutions?

I am reading "Efficient Cryptographic Schemes Provably as Secure as Subset Sum" by R. Impagliazzo and M. Naor (paper) and came across the following statement in the proof of Theorem 3.1 (pages 10-11): ...
• 849
2k views

### Solve a problem through reduction

I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard). Let's assume that you have proven that ...
• 17
615 views

• 203
2k views

### Turing reducibility implies mapping reducibility

The question is whether the following statement is true or false: $A \leq_T B \implies A \leq_m B$ I know that if $A \leq_T B$ then there is an oracle which can decide A relative to B. I know that ...
• 511
11k views

### If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B

I'm studying for my final in theory of computation, and I'm struggling with the proper way of answering whether this statement is true of false. By the definition of $\leq_m$ we can construct the ...
• 511