Skip to main content

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
4 votes
2 answers
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 ...
Nico Liu's user avatar
  • 141
4 votes
2 answers
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 ...
Arani's user avatar
  • 513
3 votes
0 answers
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 ...
Pavithran Iyer's user avatar
1 vote
1 answer
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?
user avatar
15 votes
2 answers
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}$. ...
Pavithran Iyer's user avatar
4 votes
1 answer
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 ...
Ankush's user avatar
  • 309
9 votes
4 answers
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 ...
Ankush's user avatar
  • 309
3 votes
1 answer
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 ...
asaf kalud's user avatar
5 votes
0 answers
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-...
Chao Xu's user avatar
  • 3,083
5 votes
2 answers
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 ...
John Threepwood's user avatar
2 votes
1 answer
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 ...
Joni's user avatar
  • 511
6 votes
1 answer
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 ...
John Threepwood's user avatar
19 votes
2 answers
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 ...
john's user avatar
  • 193
6 votes
1 answer
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. ...
dpll's user avatar
  • 61
8 votes
2 answers
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 ...
Numerator's user avatar
  • 472
15 votes
2 answers
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 ...
c c's user avatar
  • 503
5 votes
1 answer
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: ...
Ben Benli's user avatar
  • 103
2 votes
1 answer
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): ...
user834's user avatar
  • 849
0 votes
1 answer
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 ...
NP-Hard's user avatar
  • 17
4 votes
3 answers
615 views

Are there complete problems for P and NP under other kinds of reductions?

I know that the complexity class $\mathsf{P}$ has complete problems w.r.t. $\mathsf{NC}$ and $\mathsf{L}$ reductions. Are these two classes the only possible classes of reductions under which $\...
user2346's user avatar
  • 441
7 votes
2 answers
15k views

Reducing minimum vertex cover in a bipartite graph to maximum flow

Is it possible to show that the minimum vertex cover in a bipartite graph can be reduced to a maximum flow problem? Or to the minimum cut problem (then follow max-flow min-cut theorem, the claim holds)...
Summer_More_More_Tea's user avatar
8 votes
2 answers
995 views

Complete Problems for $DSPACE(\log(n)^k)$

We know that the $polyL$-hierarchy doesn't have complete problems, as it would conflict with the space hierarchy theorem. But: Are there complete problems for each level of this hierarchy? To be ...
Mike B.'s user avatar
  • 1,368
14 votes
2 answers
714 views

Does every NP problem have a poly-sized ILP formulation?

Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem ...
andy's user avatar
  • 253
10 votes
2 answers
6k views

Mapping Reductions to Complement of A$_{TM}$

I have a general question about mapping reductions. I have seen several examples of reducing functions to $A_{TM}$ where $A_{TM} = \{\langle M, w \rangle : \text{ For } M \text{ is a turing machine ...
RageD's user avatar
  • 203
9 votes
3 answers
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 ...
trigoman's user avatar
  • 511
11 votes
2 answers
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 ...
trigoman's user avatar
  • 511
14 votes
1 answer
746 views

Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$

We know that $st\text{-}non\text{-}connectivity$ is in $\mathsf{NL}$ by Immerman–Szelepcsényi theorem theorem and since $st\text{-}connectivity$ is $\mathsf{NL\text{-}hard}$ therefore $st\text{-}non\...
Kaveh's user avatar
  • 22.3k
2 votes
3 answers
2k views

Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs

I'm trying to solve a problem for class that is stated like so: A bipartite graph is an undirected graph in which every cycle has even length. We attempt to show that the Hamiltonian cycle (a ...
user avatar
38 votes
2 answers
20k views

How do I construct reductions between problems to prove a problem is NP-complete?

I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How ...
Anonymous's user avatar
  • 381
22 votes
3 answers
17k views

HALF CLIQUE - NP Complete Problem

Let me start off by noting this is a homework problem, please provide only advice and related observations, NO DIRECT ANSWERS please. With that said, here is the problem I am looking at: Let HALF-...
BrotherJack's user avatar
  • 1,115
1 vote
3 answers
2k views

Subset-sum and 3SAT

Two things (this may be naive): Does anyone believe there is a sub-exponential time algorithm for the Subset-sum problem? It seems obvious to me that you would have to look through all possible ...
anonymous's user avatar
  • 171
6 votes
1 answer
2k views

Reducing directed hamiltonian cycle to graph coloring

The 3-SAT problem can be reduced to both the graph coloring and the directed hamiltonian cycle problem, but is there any chain of reductions which reduce directed hamiltonian cycle to graph coloring ...
Johan Sannemo's user avatar
14 votes
2 answers
3k views

Reduction from 3-Partition problem to Balanced Partition problem

The 3-Partition problem asks whether a set of $3n$ integers can be partitioned into $n$ sets of three integers such that each set sums up to some given integer $B$. The Balanced Partition problem asks ...
Mohammad Al-Turkistany's user avatar
6 votes
1 answer
863 views

Reduction to equipartition problem from the partition problem?

Equipartition Problem: Instance: $2n$ positive integers $x_1,\dots,x_{2n}$ such that their sum is even. Let $B$ denote half their sum, so that $\sum x_{i} = 2B$. Query: Is there a subset $I \...
Shalabh's user avatar
  • 61

1
22 23 24 25
26