Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0860.68047
Lozano, A.
Bounded queries to arbitrary sets. (English)
[J] RAIRO, Inform. Théor. Appl. 30, No.2, 91-100 (1996). ISSN 0988-3754

Summary: We prove that if $\text {P}^A_{k\text{-}T}=\text {P}^A_{(k+1)\text{-}T}$ for some $k$ and an arbitrary set $A$, then $A$ is reducible to its complement under a relativized nondeterministic conjunctive reduction. By substituting $A$ by different sets, we derive some known facts such as Kadin's theorem and its extension to the class $\text{C}_=\text {P}$.

MSC 2000:: *68Q15 Complexity classes of computation

Keywords: hierarchy of sets

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]