![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
3rd SCT 1988: Georgetown University, Washington, D. C., USA
- Proceedings: Third Annual Structure in Complexity Theory Conference, Georgetown University, Washington, D. C., USA, June 14-17, 1988. IEEE Computer Society 1988, ISBN 0-8186-0794-7
- Ker-I Ko:
Relativized polynomial time hierarchies having exactly K levels. - Uwe Schöning:
The power of counting. 2-9 - Shouwen Tang, Osamu Watanabe
:
On tally relativizations of BP-complexity classes. 10-18 - Bernd Halstenberg, Rüdiger Reischuk:
Relations between communication complexity classes. 19-28 - Russell Impagliazzo
, Moni Naor:
Decision trees and downward closures. 29-38 - José L. Balcázar:
Logspace self-reducibility. 40-46 - David A. Mix Barrington, Neil Immerman, Howard Straubing:
On uniformity within NC1. 47-59 - Leonard Pitt, Manfred K. Warmuth:
Reductions among prediction problems: on the difficulty of predicting automata. 60-69 - Oscar H. Ibarra, Tao Jiang:
Trading reversals for alternation. 70-77 - Ming Li, Paul M. B. Vitányi:
Two decades of applied Kolmogorov complexity: in memoriam Andrei Nikolaevich Kolmogorov 1903-87. 80-101 - Eric Allender, Osamu Watanabe
:
Kolmogorov complexity and degrees of tally sets. 102-111 - Neil Immerman:
Nondeterministic space is closed under complementation. 112-115 - Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo
, Martin Tompa:
Two applications of complementation via inductive counting. 116-125 - Richard Edwin Stearns:
Juris Hartmanis: the beginnings of computational complexity. 128-134 - Allan Borodin:
Juris Hartmanis: building a department-building a discipline. 135-137 - Paul Young:
Juris Hartmanis: fundamental contributions to isomorphism problems. 138-154 - Lance Fortnow, John Rompel, Michael Sipser:
On the power of multi-power interactive protocols. 156-161 - Anne Condon:
Space bounded probabilistic game automata. 162-174 - Jack H. Lutz:
Pseudorandom sources for BPP. 175-180 - Ker-I Ko:
Distinguishing bounded reducibilities by sparse sets. 181-191 - Jin-Yi Cai, Lane A. Hemachandra
:
Enumerative counting is hard. 194-203 - Dung T. Huynh:
The complexity of ranking. 204-212 - Jacobo Torán:
An oracle characterization of the counting hierarchy. 213-223 - Samuel R. Buss, Louise Hay:
On truth-table reducibility to SAT and the difference hierarchy over NP. 224-233 - Ronald V. Book, Ding-Zhu Du, David A. Russo:
On polynomial and generalized complexity cores. 236-250 - Juichi Shinoda, Theodore A. Slaman:
On the theory of the PTIME degrees of the recursive sets. 252-257 - Klaus W. Wagner:
Bounded query computations. 260-277 - Jim Kadin:
The polynomial time hierarchy collapses if the Boolean hierarchy collapses. 278-292 - Luc Longpré, Paul Young:
Cook is faster than Karp: a study of reducibilities in NP. 293-302
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.