NP might not be as easy as detecting unique solutions
NP might not be as easy as detecting unique solutions
复制标题
NP 可能不像检测独特的解决方案那么容易
DOI：
10.1145/276698.276737
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
L. Fortnow
中科院分区：
文献类型：
--
作者：
R. Beigel;H. Buhrman;L. Fortnow
我们构造一个预言机 A，使得 PA = PA 和 NPA = EXPA：这个相对化世界有几个令人惊奇的属性：预言机 A 给出了第一个相对化世界，在该世界中，人们可以通过最多一个赋值来解决公式的可满足性，但 P 6= NP。预言 A 是第一个，其中 PA = UPA 6= NPA = coNPA：该构造给出了比 Fenner、Fortnow 和 Kurtz 的相对化世界简单得多的证明，其中所有 NP 完全集都是多项式时间同构的。这是第一个这样的可计算预言机。相对于 A，我们有 EXPA ZPPA PA/poly 的崩溃。我们还创建了一个不同的相对化世界，其中 NP 中存在一组 L，该集合在对 L 进行一次查询的归约下是 NP 完全的，但在传统的多一归约下是不完整的。这与 Buhrman、Spaan 和 Torenvliet 的结果形成鲜明对比，表明 NEXP 的这两个完整性概念是一致的。研究在耶鲁大学和马里兰大学完成。地址：Elect Eng Comp Science, 19 Memorial Dr W Ste 2, Bethlehem PA 180153084, USA。部分由美国国家科学基金会的 CCR-8958528、CCR-9415410 和 CCR-9700417 拨款以及 NASA 的 NAG 52895 拨款支持。电子邮件：beigel@eecs.lehigh.edu。 http://www.eecs.lehigh.edu/ beigel/ x地址：CWI, Kruislaan 413, 1098SJ 阿姆斯特丹，荷兰。部分由荷兰科学研究基金会 (NWO) 通过 SION 项目 612-34-002 提供支持，并由欧盟通过 NeuroCOLT ESPRIT 工作组 Nr. 提供部分支持。 8556，以及 HC&M 补助金编号。 ERB4050PL93-0516。电子邮件：buhrman@cwi.nl。 http://www.cwi.nl/ buhrman/ {研究是在 CWI 休假期间完成的。地址：芝加哥大学计算机科学系，1100 E. 58th。圣，芝加哥，IL 60637，美国。部分由 NSF 拨款 CCR 92-53582、荷兰科学研究基金会 (NWO) 和富布赖特学者奖支持。电子邮件：fortnow@cs.uchicago.edu。 http://www.cs.uchicago.edu/ fortnow
We construct an oracle A such that PA = PA and NPA = EXPA: This relativized world has several amazing properties: The oracle A gives the first relativized world where one can solve satisfiability on formulae with at most one assignment yet P 6= NP. The oracle A is the first where PA = UPA 6= NPA = coNPA: The construction gives a much simpler proof than that of Fenner, Fortnow and Kurtz of a relativized world where all the NP-complete sets are polynomial-time isomorphic. It is the first such computable oracle. Relative to A we have a collapse of EXPA ZPPA PA/poly. We also create a different relativized world where there exists a set L in NP that is NP-complete under reductions that make one query to L but not complete under traditional many-one reductions. This contrasts with the result of Buhrman, Spaan and Torenvliet showing that these two completeness notions for NEXP coincide. Research done at Yale and the University of Maryland. Address: Elect Eng Comp Science, 19 Memorial Dr W Ste 2, Bethlehem PA 180153084, USA. Supported in part by the National Science Foundation under grants CCR-8958528, CCR-9415410 and CCR-9700417 and by NASA under grant NAG 52895. Email: beigel@eecs.lehigh.edu. http://www.eecs.lehigh.edu/ beigel/ xAddress: CWI, Kruislaan 413, 1098SJ Amsterdam, The Netherlands. Partially supported by the Dutch foundation for scientific research (NWO) by SION project 612-34-002, and by the European Union through NeuroCOLT ESPRIT Working Group Nr. 8556, and HC&M grant nr. ERB4050PL93-0516. Email: buhrman@cwi.nl. http://www.cwi.nl/ buhrman/ {Research done while on leave at CWI. Address: University of Chicago, Department of Computer Science, 1100 E. 58th. St., Chicago, IL 60637, USA. Supported in part by NSF grant CCR 92-53582, the Dutch Foundation for Scientific Research (NWO) and a Fulbright Scholar award. Email: fortnow@cs.uchicago.edu. http://www.cs.uchicago.edu/ fortnow