%0 Journal Article
%T NP Versus PP<br>NP对PP
%A ZHAO Yun lei
%A ZHU Hong
%A ZHAO Yi ming
%A <br>赵运磊
%A 朱洪
%A 赵一鸣
%J 软件学报
%D 2001
%I 
%X In this paper, the authors mainly intend to clarify the relation between NP and PP . A randomized version of NP is given. Based on this equivalent definition of NP , another randomized complexity class is given: SUPER-NP . Although the SUPER-NP is very close to NP , but it is found surprisingly that PP?SUPER NP and thus NP?PP?SUPER-NP . In light of NP=PCP(log, O(1)) and the closeness of NP and SUPER-NP it is hoped that PP?PCP(log2,O(1)) conjecture can be peoved by showing that SUPER-NP?PCP(log2,O(1)).
%K NP
%K PP
%K PCP
%K randomized computation
%K complexity theory<br>NP
%K PP
%K PCP
%K 随机计算
%K 复杂性理论
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=8051C8C4DBA042CF&yid=14E7EF987E4155E6&vid=59906B3B2830C2C5&iid=DF92D298D3FF1E6E&sid=F131C0ADC94A25CF&eid=714E16F7CF56F343&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=7