skip to main content
article

SIGACT news complexity theory column 42

Published:01 December 2003Publication History
First page image

References

  1. {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 ScholarGoogle Scholar
  2. {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 ScholarGoogle ScholarDigital LibraryDigital Library
  3. {GHR95} R. Greenlaw, H. J. Hoover, and W. L. Ruzzo. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, New York, 1995.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. {GJ79} M. R. Garey and D. S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. {Gol77} L. M. Goldschlager. The monotone and planar circuit value problems are log-space complete for P. SIGACT News, 9:25--29, 1977.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. {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 ScholarGoogle Scholar
  7. {KK01} L. M. Kirousis and P. G. Kolaitis. The complexity of minimal satisfiability in Post's lattice. Unpublished notes, 2001.]]Google ScholarGoogle Scholar
  8. {Lad75} R. E. Ladner. The circuit value problem is log space complete for P. SIGACT News, 7(1):12--20, 1975.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. {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 ScholarGoogle Scholar
  10. {Lew79} H. R. Lewis. Satisfiability problems for propositional calculi. Mathematical Systems Theory, 13:45--53, 1979.]]Google ScholarGoogle ScholarCross RefCross Ref
  11. {Pip97} N. Pippenger. Theories of Computability. Cambridge University Press, Cambridge, 1997.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. {Pos41} E. L. Post. The two-valued iterative systems of mathematical logic. Annals of Mathematical Studies, 5:1--122, 1941.]]Google ScholarGoogle Scholar
  13. {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 ScholarGoogle ScholarCross RefCross Ref
  14. {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 ScholarGoogle ScholarDigital LibraryDigital Library
  15. {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 ScholarGoogle Scholar
  16. {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 ScholarGoogle Scholar
  17. {Ugo88} A. B. Ugolnikov. Closed Post classes. Izvestiya VUZ. Matematika, 32:79--88 (131--142), 1988.]]Google ScholarGoogle Scholar
  18. {Vol99} H. Vollmer. Introduction to Circuit Complexity -- A Uniform Approach. Texts in Theoretical Computer Science. Springer Verlag, Berlin Heidelberg, 1999.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. {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 ScholarGoogle Scholar

Index Terms

  1. SIGACT news complexity theory column 42
    Index terms have been assigned to the content through auto-classification.

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in

    Full Access

    • Published in

      cover image ACM SIGACT News
      ACM SIGACT News  Volume 34, Issue 4
      December 2003
      80 pages
      ISSN:0163-5700
      DOI:10.1145/954092
      Issue’s Table of Contents

      Copyright © 2003 Author

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 1 December 2003

      Check for updates

      Qualifiers

      • article

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader