PP is closed under truth-table reductions

被引：16

作者：

Fortnow, L ^{[1
]}

Reingold, N ^{[1
]}

机构：

[1] YALE UNIV,NEW HAVEN,CT 06520

来源：

INFORMATION AND COMPUTATION | 1996年 / 124卷 / 01期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1006/inco.1996.0001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Beigel, Reingold, and Spielman (J. Comput System Sci 50, 191-202 (1995)) showed that PP is closed under intersection and a variety of special cases of polynomial-time truth-table closure. We extend their techniques to show that PP is closed under general polynomial-time truth-table reductions. We also show that PP is closed under constant-round truth-table reductions. (C) 1996 Academic Press, Inc.

引用

页码：1 / 6

页数：6

共 6 条

[1]

Babai L., 1991, Computational Complexity, V1, P41, DOI 10.1007/BF01200057

[2] PP IS CLOSED UNDER INTERSECTION [J].