PP IS CLOSED UNDER TRUTH-TABLE REDUCTIONS

Authors
FORTNOW L REINGOLD N
Citation
L. Fortnow et N. Reingold, PP IS CLOSED UNDER TRUTH-TABLE REDUCTIONS, Information and computation, 124(1), 1996, pp. 1-6
Citations number
6
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
124
Issue
1
Year of publication
1996
Pages
1 - 6
Database
ISI
SICI code
0890-5401(1996)124:1<1:PICUTR>2.0.ZU;2-X
Abstract
Beigel, Reingold, and Spielman (J. Comput System Sci 50, 191-202 (1995 )) showed that PP is closed under intersection and a variety of specia l cases of polynomial-time truth-table closure. We extend their techni ques to show that PP is closed under general polynomial-time truth-tab le reductions. We also show that PP is closed under constant-round tru th-table reductions. (C) 1996 Academic Press, Inc.