- {Böh01} E. Böhler. On the relative complexity of Post's classes. Technical Report 286, Fachbereich Mathematik und Informatik, Universität Würzburg, 2001.]]Google Scholar
- {Coo71} S. A. Cook. Characterizations of pushdown machines in terms of time-bounded computers. Journal of the Association for Computing Machinery, 18:4--18, 1971.]] Google ScholarDigital Library
- {GHR95} R. Greenlaw, H. J. Hoover, and W. L. Ruzzo. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, New York, 1995.]] Google ScholarDigital Library
- {GJ79} M. R. Garey and D. S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.]] Google ScholarDigital Library
- {Gol77} L. M. Goldschlager. The monotone and planar circuit value problems are log-space complete for P. SIGACT News, 9:25--29, 1977.]] Google ScholarDigital Library
- {JGK70} S. W. Jablonski, G. P. Gawrilow, and W. B. Kudrjawzew. Boolesche Funktionen und Postsche Klassen, volume 6 of Logik und Grundlagen der Mathematik. Friedr. Vieweg & Sohn and C. F. Winter'sche Verlagsbuchhandlung, Braunschweig and Basel, 1970.]]Google Scholar
- {KK01} L. M. Kirousis and P. G. Kolaitis. The complexity of minimal satisfiability in Post's lattice. Unpublished notes, 2001.]]Google Scholar
- {Lad75} R. E. Ladner. The circuit value problem is log space complete for P. SIGACT News, 7(1):12--20, 1975.]] Google ScholarDigital Library
- {Lev73} L. A. Levin. Universal sorting problems. Problemi Peredachi Informatsii, 9(3):115--116, 1973. English translation: Problems of Information Transmission, 9(3):265--266.]]Google Scholar
- {Lew79} H. R. Lewis. Satisfiability problems for propositional calculi. Mathematical Systems Theory, 13:45--53, 1979.]]Google ScholarCross Ref
- {Pip97} N. Pippenger. Theories of Computability. Cambridge University Press, Cambridge, 1997.]] Google ScholarDigital Library
- {Pos41} E. L. Post. The two-valued iterative systems of mathematical logic. Annals of Mathematical Studies, 5:1--122, 1941.]]Google Scholar
- {Rei03} S. Reith. On the complexity of some equivalence problems for propositional calculi. In Proceedings 28th International Symposium on Mathematical Foundations of Computer Science, pages 632--641, 2003.]]Google ScholarCross Ref
- {RV00} S. Reith and H. Vollmer. Optimal satisfiability for propositional calculi and constraint satisfaction problems. In Proceedings 25th International Symposium on Mathematical Foundations of Computer Science, volume 1893 of Lecture Notes in Computer Science, pages 640--649. Springer Verlag, 2000.]] Google ScholarDigital Library
- {RW00} S. Reith and K. W. Wagner. The complexity of problems defined by Boolean circuits. Technical Report 255, Institut für Informatik, Universität Würzburg, 2000. To appear in Proceedings International Conference Mathematical Foundation of Informatics, Hanoi, Oct. 25--28, 1999.]]Google Scholar
- {Sze86} Á. Szendrei. Clones in Universal Algebra. Séminaire de mathématiques supérieures, NATO Advanced Study Institute. Les Presses de l'Université de Montréal, Montréal, 1986.]]Google Scholar
- {Ugo88} A. B. Ugolnikov. Closed Post classes. Izvestiya VUZ. Matematika, 32:79--88 (131--142), 1988.]]Google Scholar
- {Vol99} H. Vollmer. Introduction to Circuit Complexity -- A Uniform Approach. Texts in Theoretical Computer Science. Springer Verlag, Berlin Heidelberg, 1999.]] Google ScholarDigital Library
- {Zve00} I. E. Zverovich. Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes. Technical Report 17-2000, Rutgers Center for Operations Research, Rutgers University, 2000.]]Google Scholar
Index Terms
SIGACT news complexity theory column 42
Recommendations
SIGACT News Complexity Theory Column 117: Thirty Years of Complexity Theory (Columns)
It has been a tremendous treat being the SIGACT News Complexity Theory Column editor for these past thirty years. I thought about what to say here, and realized it is pretty simple: Thank you.
Comments