Previous slide Next slide Back to the first slide View text 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.