A TIGHT RELATIONSHIP BETWEEN GENERIC ORACLES AND TYPE-2 COMPLEXITY THEORY

Authors
COOK S IMPAGLIAZZO R YAMAKAMI T
Citation
S. Cook et al., A TIGHT RELATIONSHIP BETWEEN GENERIC ORACLES AND TYPE-2 COMPLEXITY THEORY, Information and computation, 137(2), 1997, pp. 159-170
Citations number
32
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
137
Issue
2
Year of publication
1997
Pages
159 - 170
Database
ISI
SICI code
0890-5401(1997)137:2<159:ATRBGO>2.0.ZU;2-A
Abstract
We show that any two complexity classes satisfying some general condit ions are distinct relative to a generic oracle iff the corresponding t ype-2 classes are distinct. (C) 1997 Academic Press.