Skip to Main Content
Theory of Computational Complexity, 2nd Edition
book

Theory of Computational Complexity, 2nd Edition

by Ding-Zhu Du, Ker-I Ko
June 2014
Intermediate to advanced content levelIntermediate to advanced
512 pages
17h 55m
English
Wiley
Content preview from Theory of Computational Complexity, 2nd Edition

Chapter 9

Complexity of Counting

How do I love thee? Let me count the ways.
I love thee to the depth and breadth and height
My soul can reach.

—Elizabeth Barrett Browning

Informally, the complexity class NP contains the decision problems in which an input instance is accepted if and only if there exists a good witness. The complexity classes PP and BPP contain the problems in which an input instance is accepted if and only if the majority of the witnesses are good. All these problems are just the restricted forms of a more general counting problem: for any input instance, count the number of good witnesses for it. Such counting problems occur very often in practical problems. For instance, for the HAMILTONIAN CIRCUIT problem, one is often interested not only in the existence of a Hamiltonian circuit in a graph but also interested in the total number of different Hamiltonian circuits. In this chapter, we study the complexity of these counting problems and its relation to the complexity of nondeterministic and probabilistic computation. We define two complexity classes, #P and c09-math-0002, of counting problems. The main result of this chapter shows that decision problems in the polynomial-time hierarchy are polynomial-time reducible to counting problems in these complexity classes. We also investigate the relation between the relativized #P and the relativized polynomial-time hierarchy. ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Theory of Computation

Theory of Computation

George Tourlakis

Publisher Resources

ISBN: 9781118594971Purchase book