SEPARATING THE POLYNOMIAL-TIME HIERARCHY BY ORACLES.

Andrew Chi Chih Yao

doi:10.1109/sfcs.1985.49

SEPARATING THE POLYNOMIAL-TIME HIERARCHY BY ORACLES.

Andrew Chi Chih Yao

Faculty of Electronic and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

394 Scopus citations

Abstract

Exponential lower bounds are presented on the size of depth-k Boolean circuits for computing certain functions. These results imply that there exists an oracle set A such that, relative to A, all the levels in the polynomial-time hierarchy are distinct.

Original language	English
Title of host publication	Annual Symposium on Foundations of Computer Science (Proceedings)
Publisher	IEEE
Pages	1-10
Number of pages	10
ISBN (Print)	0818606444, 9780818606441
DOIs	https://doi.org/10.1109/sfcs.1985.49
State	Published - 1985

Publication series

Name	Annual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)	0272-5428

Access to Document

10.1109/sfcs.1985.49

Cite this

@inproceedings{77c9b06b8bfc45088a4074aa29a23354,

title = "SEPARATING THE POLYNOMIAL-TIME HIERARCHY BY ORACLES.",

abstract = "Exponential lower bounds are presented on the size of depth-k Boolean circuits for computing certain functions. These results imply that there exists an oracle set A such that, relative to A, all the levels in the polynomial-time hierarchy are distinct.",

author = "Yao, \{Andrew Chi Chih\}",

year = "1985",

doi = "10.1109/sfcs.1985.49",

language = "英语",

isbn = "0818606444",

series = "Annual Symposium on Foundations of Computer Science (Proceedings)",

publisher = "IEEE",

pages = "1--10",

booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",

}

TY - GEN

T1 - SEPARATING THE POLYNOMIAL-TIME HIERARCHY BY ORACLES.

AU - Yao, Andrew Chi Chih

PY - 1985

Y1 - 1985

N2 - Exponential lower bounds are presented on the size of depth-k Boolean circuits for computing certain functions. These results imply that there exists an oracle set A such that, relative to A, all the levels in the polynomial-time hierarchy are distinct.

AB - Exponential lower bounds are presented on the size of depth-k Boolean circuits for computing certain functions. These results imply that there exists an oracle set A such that, relative to A, all the levels in the polynomial-time hierarchy are distinct.

UR - https://www.scopus.com/pages/publications/0022201594

U2 - 10.1109/sfcs.1985.49

DO - 10.1109/sfcs.1985.49

M3 - 会议稿件

AN - SCOPUS:0022201594

SN - 0818606444

SN - 9780818606441

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 1

EP - 10

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - IEEE

ER -

SEPARATING THE POLYNOMIAL-TIME HIERARCHY BY ORACLES.

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this