The 2024 Developer Survey results are live! See the results

# Questions tagged [reductions]

A reduction is the transformation of one problem into another problem. A example of using a reduction would be to be to show if a problem P is undecidable. This would be achieved by transforming or performing a reduction of a decision problem $P$ into an undecidable problem. If this can be achieved then we have shown that this problem P is undecidable.

35 questions
Filter by
Sorted by
Tagged with
7k views

### Many-one reductions vs. Turing reductions to define NPC

Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions?
• 1,668
2k views

### Derandomizing Valiant-Vazirani?

The Valiant-Vazirani theorem says that if there is a polynomial time algorithm (deterministic or randomized) for distinguishing between a SAT formula that has exactly one satisfying assignment, and an ...
• 3,798
5k views

• 478
462 views

### Is there a FNP problem that's NP-hard but not FNP-hard?

For the reductions, choose a class C such that [it's clear what FC means] and FC is not known to be able to solve the satisfaction search problem, and assume that FC indeed can't solve that search ...
2k views

### Is there simple reduction Dominating Set to Vertex Cover?

Is there simple reduction Dominating Set to Vertex Cover? In the other direction the reduction is simple. Searching the web returned blog. It warns This is not finished yet and experiments suggest ...
• 1,955
171 views

### What is conjunctive truth table reduction?

What are conjunctive/disjunctive truth table reductions and how do they compare with other reductions?
• 13.1k
1 vote
Let the k-inequality-MIS problem be the decision problem whether an arbitrary graph $G=(V, E)$ contains a maximal independent set of at least size $k$, that is the corresponding language is: \...