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 relating these classes to each other. A computational problem is a task solved by ...

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. 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 which converts instances of one decision problem L_1 into instances of a second decision problem L_2 where the instan ...

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 of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

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 so ...

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 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 performed by ...

. 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, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...

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), ...

X=g\circ Y\circ f

. Alternatively, expressed in terms of

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

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, un ...

as the function

g

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

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" or "number P complete") form a complexity class in computational complexity theory. The problems in this complexity class are defined by having the following two properties: *The problem is ...

. (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.) 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 (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

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