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

### Turing reducibility of 2 versions of the satisfiability problem

I need help with this problem. There are 2 versions of the satisfiability problem:  decision version: determine whether an arbitrary formula f is satisfiable or not  search ...
30 views

### NPC PROBLEM minimum sum of vertex coloring

For a graph G and a legal vertex-colouring ψ : V(G)→N of G, let σψ(G) be the sum of ψ(v), and set σ(G):=min σψ(G), where the minimum ranges over all valid vertex colourings of G. Prove that {(...
111 views

### A non-polynomial reduction

Given two problems $P_1$ and $P_2$. $P_1$ is NP-complete in the strong sense and we want to prove that $P_2$ is also NP-complete but the reduction from $P_1$ to $P_2$ is not polynomial. Can we say ...
109 views

### Karp reduction from optimization problems to decision problems

When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other. Focusing on Cook reductions, there exists a natural Karp ...
81 views

### Prove that $\#k-colouring$ graph problem is $\#P-complete$

I need to prove, that the $\#k-colouring$ graph problem is $\#P-complete$. I want to construct the reduction from $\#3SAT$ problem, so $\#3SAT \leq \#k-colouring$. The reduction between the counting ...
3k views

### Poly-time reduction from ILP to SAT?

So, as is known, ILP's 0-1 decision problem is NP-complete. Showing it's in NP is easy, and the original reduction was from SAT; since then, many other NP-Complete problems have been shown to have ILP ...
99 views

### Scheduling to minimize the truncated gaps

I have a single job of unit length, a set of $n$ slots, and a budget of $B$ units. If the job is scheduled at slot $t$, then it will consume $c(t)$ units of the budget $B$. If the job is not scheduled ...
21 views

### Computing Every Path from a Source to Multiple Destinations [Simpler Algorithm]

How are these two problems different? I. Find all paths between a source vertex and destination vertex. II. Find all paths between a source vertex and all vertices in the graph. Both of these ...