PP Is Closed under Intersection

✍ Scribed by R. Beigel; N. Reingold; D. Spielman

• Book ID: 102970579
• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 834 KB
• Volume: 50
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1995.1017

✦ Synopsis

In this seminal paper on probabilistic Turing machines, Gill asked whether the class PP is closed under intersection and union. We give a positive answer to this question. We also show that (P P) is closed under a variety of polynomial-time truth-table reductions. Consequences in complexity theory include the definite collapse and (assuming (P \neq P P) ) separation of certain query hierarchies over PP. Similar techniques allow us to combine several threshold gates into a single threshold gate. Consequences in the study of circuits include the simulation of circuits with a small number of threshold gates by circuits having only a single threshold gate at the root (perceptrons) and a lower bound on the number of threshold gates that are needed to compute the parity function. 1995 Academic Press, Inc.