In the

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

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 In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of f ...

. These reductions may also be called polynomial many-one counting reductions or weakly parsimonious reductions; they are analogous to

many-one reduction In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction that converts instances of one decision problem (whether an instance is in L_1) to another decision problem (whether ...

s for

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...

s and they generalize the

parsimonious reduction In computational complexity theory and game complexity, a parsimonious reduction is a transformation from one problem to another (a reduction) that preserves the number of solutions. Informally, it is a bijection between the respective sets of sol ...

Definition

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

X

into instances of another problem

Y

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

f

and

g

, both of which must be computable in

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

. The function

f

transforms inputs for

X

into inputs for

Y

, and the function

g

transforms outputs for

Y

into outputs for

X

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

x

for problem

X

to an input

y=f(x)

for problem

Y

, and then one solves

y

to produce an output

z

. It must be the case that the transformed output

g(z)

is the correct output for the original input

x

. That is, if the input-output relations of

X

and

Y

are expressed as functions, then their

function composition In mathematics, the composition operator \circ takes two function (mathematics), functions, f and g, and returns a new function h(x) := (g \circ f) (x) = g(f(x)). Thus, the function is function application, applied after applying to . (g \c ...

must obey the

identity Identity may refer to: * Identity document * Identity (philosophy) * Identity (social science) * Identity (mathematics) Arts and entertainment Film and television * ''Identity'' (1987 film), an Iranian film * ''Identity'' (2003 film), an ...

X=g\circ Y\circ f

. Alternatively, expressed in terms of

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

s, one possible algorithm for solving

X

would be to apply

f

to transform the problem into an instance of

Y

, solve that instance, and then apply

g

to transform the output of

Y

into the correct answer for

X

Relation to other kinds of reduction

As a special case, a

is a polynomial-time transformation

f

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 Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, unc ...

as the function

g

Applications in complexity theory

A functional problem (specified by its inputs and desired outputs) belongs to the complexity class

if there exists a

non-deterministic Turing machine In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...

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

Y

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

X

in ♯P to

Y

. If, in addition,

Y

itself belongs to ♯P, then

Y

is said to be

♯P-complete The #P-complete problems (pronounced "sharp P complete", "number P complete", or "hash P complete") form a complexity class in computational complexity theory. The problems in this complexity class are defined by having the following two properti ...

. (Sometimes, as in Valiant's original paper proving the completeness of the permanent of 0–1 matrices, a weaker notion of reduction,

Turing reduction In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine that decides problem A given an oracle for B (Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an algorithm ...

, is instead used for defining ♯P-completeness.) The usual method of proving a problem

Y

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

X

and find a polynomial-time counting reduction from

X

Y

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

Y

, obtained by composing a reduction from the other problem to

X

with the reduction from

X

Y

References

{{reflist, refs= {{citation , last1 = Creignou , first1 = Nadia , last2 = Khanna , first2 = Sanjeev , author2-link = Sanjeev Khanna , last3 = Sudan , first3 = Madhu , author3-link = Madhu Sudan , contribution = 2.2.2 Parsimonious reductions and ♯P-completeness , contribution-url = https://books.google.com/books?id=ZzW5AgAAQBAJ&pg=PA12 , doi = 10.1137/1.9780898718546 , isbn = 0-89871-479-6 , mr = 1827376 , pages = 12–13 , publisher = Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA , series = SIAM Monographs on Discrete Mathematics and Applications , title = Complexity classifications of Boolean constraint satisfaction problems , year = 2001 {{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 , editor2-link = Marijn Heule , 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 particula
pp. 634–635
{{citation , last = Valiant , first = L. G. , authorlink = Leslie Valiant , doi = 10.1016/0304-3975(79)90044-6 , issue = 2 , journal =

Theoretical Computer Science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

, mr = 526203 , pages = 189–201 , title = The complexity of computing the permanent , volume = 8 , year = 1979, doi-access = free Reduction (complexity)