# 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,146 questions
Filter by
Sorted by
Tagged with
288 views

### Reduction of A_LBA to E_LBA

I have a rather interesting one to ponder and would love if I could get an answer for it. We were discussing the topic of mapping reduction today in my Computing theory course and I was wondering why ...
2k views

13k 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)...
849 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 ...
550 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 ...
5k views

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 ...
14k 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 ...
14k 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-...
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 ...
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 ...
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 ...
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 \...