| Previous slide | Next slide | Back to the first slide | View Graphic Version |
PP is the class of languages defined by NP machines where a string is in the language if the accepting paths outnumber the rejecting paths.
PP - defined by GIll on seminal paper on probabilistic computation. Well known to be closed under complement but left open if closed under intersection.