1

T Thierauf, The Boolean isomorphism problem, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.422, October 14-16, 1996

2

Miklos Ajtai , Ronald Fagin , Larry Stockmeyer, The closure of monadic NP, Journal of Computer and System Sciences, v.60 n.3, p.660-716, June 2000  [doi>10.1006/jcss.1999.1691]

3

Piotr Berman , Marek Karpinski , Lawrence L. Larmore , Wojciech Plandowski , Wojciech Rytter, On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, p.40-51, June 30-July 02, 1997

4

[4] B. Borchert and D. Ranjan. The circuit subfunction relations are ¿2^p-complete. Research Report MPI-I-93-121, Max-Planck-Institut fr Informatik, Im Stadtwald, D-66123 Saarbrcken, Germany, May 1993.

5

[5] B. Borchert, D. Ranjan, and F. Stephan. On the computational complexity of some classical equivalence relations on boolean functions. MST: Mathematical Systems Theory, 31, 1998.

6

[6] E. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Springer Verlag, Berlin, 1997.

7

[7] S. A. Burr. Some undecidable problems involving the edge-coloring and vertex-coloring of graphs. Discrete Mathematics, 50:171-177, 1984.

8

[8] S. A. Burr. On the Computational Complexity of Ramsey-Type Problems. In Ne¿et¿il and Rödl, editors, Mathematics of Ramsey Theory. Springer-Verlag, 1990.

9

Anne Condon , Joan Feigenbaum , Carsten Lund , Peter Shor, Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.305-314, May 16-18, 1993, San Diego, California, United States  [doi>10.1145/167088.167190]

10

[10] D.-Z. Du and K.-I. Ko. Theory of Computational Complexity. Wiley, 2000.

11

[11] T. Eiter and G. Gottlob. Note on the complexity of some eigenvector problems. Technical Report CD-TR 95/89, Christian Doppler Laboratory for Expert Systems, TU Vienna, Dec. 1995.

12

Joan Feigenbaum , Jeremy A. Kahn , Carsten Lund, Complexity results for POMSET languages, SIAM Journal on Discrete Mathematics, v.6 n.3, p.432-442, Aug. 1993  [doi>10.1137/0406035]

13

[13] L. Fortnow and J. Killian, April 2002. Personal communication.

14

[14] M. R. Garey and D. S. Johnson. Computers and Intractability. Freeman, San Francisco, 1979.

15

[15] D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete and Computational Geometry , 2:127-151, 1987.

16

Edith Hemaspaandra , Gerd Wechsung, The Minimization Problem for Boolean Formulas, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.575, October 19-22, 1997

17

Rodney R. Howell , Louis E. Rosier, Completeness results for conflict-free vector replacement systems, Journal of Computer and System Sciences, v.37 n.3, p.349-366, Dec. 1988  [doi>10.1016/0022-0000(88)90013-X]

18

Rodney R. Howell , Louis E. Rosier , Hsu-Chun Yen, Normal and sinkless Petri nets, Journal of Computer and System Sciences, v.46 n.1, p.1-26, Feb. 1993  [doi>10.1016/0022-0000(93)90046-Y]

19

Dung T. Huynh, Deciding the inequivalence of context-free grammars with 1-letter terminal alphabet is &Sgr;p-2--complete, Theoretical Computer Science, v.33 n.2-3, p.305-326, Oct., 1984  [doi>10.1016/0304-3975(84)90092-6]

20

[20] T.-D. Huynh. The Complexity of Semilinear Sets. Journal of Information Processing and Cybernetics, 18(6):291-338, 1982.

21

[21] M. A. Kiwi, C. Lund, A. Russell, D. A. Spielman, and R. Sundaram. Alternation in interaction. In Structure in Complexity Theory Conference, pages 294-303, 1994.

22

[22] K.-I. Ko and C.-L. Lin. On the complexity of min-max optimization problems and their approximation. In D.-Z. Du and P. M. Pardalos, editors, Minimax and Applications, pages 219-239. Kluwer Academic Publishers, Boston, 1995.

23

[23] K.-I. Ko and C.-L. Lin. On the longest circuit in an alterable digraph. Journal of Global Optimization, 7:279-295, 1995.

24

[24] K.-I. Ko and W.-G. Tzeng. Three ¿2^p-complete Problems in Computational Learning Theory. Computational Complexity, 1:269-310, 1991.

25

Evangelos Kranakis , Danny Krizanc , Berthold Ruf , Jorge Urrutia , Gerhard Woeginger, The VC-dimension of set systems defined by graphs, Discrete Applied Mathematics, v.77 n.3, p.237-257, Aug. 22, 1997  [doi>10.1016/S0166-218X(96)00137-0]

26

Chih-Long Lin, Optimizing TRIEs for ordered pattern matching is /spl Pi//sub 2//sup P/-complete, Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), p.238, June 19-22, 1995

27

Alain J. Mayer , Larry J. Stockmeyer, The complexity of word problems—this time with interleaving, Information and Computation, v.115 n.2, p.293-311, Dec. 1994  [doi>10.1006/inco.1994.1098]

28

[28] A. R. Meyer and L. J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In 13th Annual Symposium on Switching and Automata Theory, pages 125-129, The University of Maryland, 25-27 Oct. 1972. IEEE.

29

Elchanan Mossel , Christopher Umans, On the Complexity of Approximating the VC Dimension, Proceedings of the 16th Annual Conference on Computational Complexity, p.220, June 18-21, 2001

30

Elchanan Mossel , Christopher Umans, On the Complexity of Approximating the VC Dimension, Proceedings of the 16th Annual Conference on Computational Complexity, p.220, June 18-21, 2001

31

[31] C. H. Papadimitriou. Computational Complexity. Addison-Wesley, New York, 1994.

32

Christos H. Papadimitriou , Mihalis Yannakakis, On limited nondeterminism and the complexity of the V-C dimension, Journal of Computer and System Sciences, v.53 n.2, p.161-170, Oct. 1996  [doi>10.1006/jcss.1996.0058]

33

V Rutenberg, Complexity of generalized graph coloring, Proceedings of the 12th symposium on Mathematical foundations of computer science 1986, p.537-581, June 1986, Bratislava, Czechoslovakia

34

Wojciech Rytter, Algorithms on Compressed Strings and Arrays, Proceedings of the 26th Conference on Current Trends in Theory and Practice of Informatics on Theory and Practice of Informatics, p.48-65, November 27-December 04, 1999

35

Marcus Schaefer, Graph Ramsey theory and the polynomial hierarchy, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.592-601, May 01-04, 1999, Atlanta, Georgia, United States  [doi>10.1145/301250.301411]

36

[36] M. Schaefer. Deciding the Vapnik-Cervonenkis dimension is ¿3^p-complete, ii. Technical Report TR00- 006, DePaul University, Oct. 2000.

37

[37] M. Schaefer and C. Umans. ¿2^p-completeness of MIN DNF TAUTOLOGY. Manuscript, Apr. 2002.

38

Marcus Schaefer, Deciding the Vapnik-Ccaron;ervonenkis dimension is S^p3 -complete, Journal of Computer and System Sciences, v.58 n.1, p.177-182, Feb. 1999  [doi>10.1006/jcss.1998.1602]

39

[39] L. Stockmeyer and D. S. Modha. Links between complexity theory and constrained block coding. IEEE Transactions on Information Theory, 48(1):59-88, 2002.

40

[40] L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3(1):1-22, Oct. 1976.

41

Amnon Ta-Shma , Christopher Umans , David Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.143-152, July 2001, Hersonissos, Greece  [doi>10.1145/380752.380790]

42

[42] T. Tantau. A note on the complexity of the reachability problem for tournaments. Technical Report TR01-092, ECCC, Nov. 2001.

43

Christopher Umans, Hardness of Approximating Minimization Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.465, October 17-18, 1999

44

Christopher Umans, On the Complexity and Inapproximability of Shortest Implicant Problems, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.687-696, July 11-15, 1999

45

Christopher Matthew Umans , Christos H. Papadimitriou, Approximability and completeness in the polynomial hierarchy, University of California, Berkeley, 2000

46

Christopher Umans, The minimum equivalent DNF problem and shortest implicants, Journal of Computer and System Sciences, v.63 n.4, p.597-611, December 2001  [doi>10.1006/jcss.2001.1775]

47

Klaus W. Wagner, The complexity of combinatorial problems with succinct input representation, Acta Informatica, v.23 n.3, p.325-356, June 1986  [doi>10.1007/BF00289117]

48

[48] C. Wrathall. Complete sets and the polynomial-time hierarchy. Theoretical Computer Science, 3(1):23- 33, Oct. 1976.

Lane A. Hemaspaandra: colleagues