\(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
type: Item
instance of: scholarly article
title: \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
zbMATH Open document ID: 0693.68027
DOI: 10.1016/0022-0000(89)90024-X
author: Jim Kadin
published in: Journal of Computer and System Sciences
publication date: 1989-01-01T00:00:00Z
review text: It has been known (\textit{S. Mahaney} [J. Comput. Syst. Sci. 25, 130-143 (1987; Zbl 0493.68043)] that the polynomial hierarchy collapses to \(P^{NP}\) if NP has a \(\leq^ P_ T\)-complete sparse set. The author improves this result by replacing \(N^{NP}\) with \(P^{NP[O(\log n)]}\), where this latter class is the class of all languages acceptable by deterministic polynomial time machines making only O(log n) queries to an NP-oracle. This result is a consequence of the following one: If for a sparse S in NP it holds that \(coNP\subseteq NP^ S\), then \(PH\subseteq P^{NP[O(\log n)]}\). This collapse result is optimal in the following sense: For any function \(f(n)=o(\log n)\) there exists a set B for which \(NP^ B\) has a sparse \(\leq^ P_ T\)-complete set and \((P^ B)^{NP^ B[O(\log n)]}\subseteq (P^ B)^{NP^ B[f(n)]}.\) Furthermore, the paper exhibits \(\leq^ P_ m\)-complete problems for \(P^{NP[O(\log n)]}\) and discusses conditions fo the class of languages \(\leq^ P_ m\)-reducible to a set C to be equal to \(P^{C[O(\log n)]}\). For \(D^ P=\{X\cap Y :\) \(X\in NP\wedge Y\in coNP\}\) it is shown: If \(D^ P=coD^ P\), then \(P^{NP[O(\log n)]}\subseteq D^ P\).
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4135400
zbMATH Keywords: sparse complete sets
zbMATH Keywords: query restricted oracle use
zbMATH Keywords: collapse of the polynomial time hierarchy
zbMATH Keywords: NP optimization problems
MaRDI profile type: Publication
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: On the unique satisfiability problem
cites work: The Boolean Hierarchy I: Structural Properties
cites work: On relativized exponential and probabilistic complexity classes
cites work: The strong exponential hierarchy collapses
cites work: Q3862379
cites work: Relativizing relativized computations
cites work: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
cites work: Turing machines that take advice
cites work: The complexity of optimization problems
cites work: A comparison of polynomial time reducibilities
cites work: A note on sparse oracles for NP
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: On the complexity of unique solutions
cites work: The complexity of facets (and some facets of complexity)
cites work: Q4743737
cites work: The polynomial-time hierarchy
cites work: Q3766851
cites work: Bounded Query Classes
cites work: Relativized circuit complexity
cites work: Some consequences of non-uniform conditions on uniform classes
description: scientific article; zbMATH DE number 4135400