文章基本信息

标题：Sparse sets, approximable sets, and parallel queries to NP
本地全文：下载
作者：Vikraman Arvind, Jacobo Toran
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We relate the existence of disjunctive hard sets for NP to other well studied hypotheses in complexity theory showing that if an NP-complete set or a coNP-complete set is polynomial-time disjunctively reducible to a sparse set then FPNP = FPNP[log]. Using a similar argument we obtain also that if SAT is O(logn)-approximable then FPNP = FPNP[log]. Since FPNP = FPNP[log]. implies that SAT is O(\logn)-approximable, these two hypotheses are shown to be equivalent, thus solving an open question from Buhrman Fortnow and Torenvliet. We show as a consequence of our first result that if an NP-complete set or a coNP-complete set is disjunctively reducible to a sparse set of polylogarithmic density then P=NP.
关键词：approximable sets, parallel queries, Reducibilities, Sparse sets