“Polynomial-time counting reduction”的意思、由来-开放百科全书

In the computational complexity theory of counting problems, a polynomial-time counting reduction is a type of reduction (a transformation from one problem to another) used to define the notion of completeness for the complexity class ♯P.{{r|gss}} These reductions may also be called polynomial many-one counting reductions or weakly parsimonious reductions; they are analogous to many-one reductions for decision problems and they generalize the parsimonious reductions.{{r|cks}}

Definition

A polynomial-time counting reduction is usually used to transform instances of a known-hard problem

into instances of another problem

that is to be proven hard. It consists of two functions

and

, both of which must be computable in polynomial time. The function

transforms inputs for

into inputs for

, and the function

transforms outputs for

into outputs for

.{{r|gss|cks}}

These two functions must preserve the correctness of the output. That is, suppose that one transforms an input

for problem

to an input

for problem

, and then one solves

to produce an output

. It must be the case that the transformed output

is the correct output for the original input

. That is, if the input-output relations of

and

are expressed as functions, then their function composition must obey the identity

. Alternatively, expressed in terms of algorithms, one possible algorithm for solving

would be to apply

to transform the problem into an instance of

, solve that instance, and then apply

to transform the output of

into the correct answer for

.{{r|gss|cks}}

Relation to other kinds of reduction

As a special case, a parsimonious reduction is a polynomial-time transformation

on the inputs to problems that preserves the exact values of the outputs. Such a reduction can be viewed as a polynomial-time counting reduction, by using the identity function as the function

.{{r|gss|cks}}

Applications in complexity theory

A functional problem (specified by its inputs and desired outputs) belongs to the complexity class ♯P if there exists a non-deterministic Turing machine that runs in polynomial time, for which the output to the problem is the number of accepting paths of the Turing machine. Intuitively, such problems count the number of solutions to problems in the complexity class NP. A functional problem

is said to be ♯P-hard if there exists a polynomial-time counting reduction from every problem

in ♯P to

. If, in addition,

itself belongs to ♯P, then

is said to be ♯P-complete.{{r|gss|cks}} (Sometimes, as in Valiant's original paper proving the completeness of the permanent of 0–1 matrices, a weaker notion of reduction, Turing reduction, is instead used for defining ♯P-completeness.{{r|val}})

The usual method of proving a problem

in ♯P to be ♯P-complete is to start with a single known ♯P-complete problem

and find a polynomial-time counting reduction from

. If this reduction exists, then there exists a reduction from any other problem in ♯P to

, obtained by composing a reduction from the other problem to

with the reduction from

.{{r|gss|cks}}

References

1. ^{{citation | last1 = Gomes | first1 = Carla P. | author1-link = Carla Gomes | last2 = Sabharwal | first2 = Ashish | last3 = Selman | first3 = Bart | author3-link = Bart Selman | editor1-last = Biere | editor1-first = Armin | editor2-last = Heule | editor2-first = Marijn | editor3-last = van Maaren | editor3-first = Hans | editor4-last = Walsh | editor4-first = Toby | contribution = Chapter 20. Model Counting | isbn = 9781586039295 | pages = 633–654 | publisher = IOS Press | series = Frontiers in Artificial Intelligence and Applications | title = Handbook of Satisfiability | url = http://www.cs.cornell.edu/~sabhar/chapters/ModelCounting-SAT-Handbook-prelim.pdf | volume = 185 | year = 2009}}. See in particular [https://books.google.com/books?id=YVSM3sxhBhcC&pg=PA634 pp. 634–635].
2. ^{{citation | last = Valiant | first = L. G. | authorlink = Leslie Valiant | doi = 10.1016/0304-3975(79)90044-6 | issue = 2 | journal = Theoretical Computer Science | mr = 526203 | pages = 189–201 | title = The complexity of computing the permanent | volume = 8 | year = 1979}}