Computational Complexity on the Blackboard

• Autorzy: Kopczyński E.

Identyfikatory

DOI

10.3233/FI-2017-1523

• Języki publikacji: EN

Abstrakty

EN

This paper is an introduction to the computational complexity theory. I believe that the standard courses in complexity theory make some things much more important than they really are, while things which I find extremely interesting are marginalized. Thus, it can be seen as my subjective view on what is important and interesting in computational complexity, and what is not. We state the basic facts from computational complexity theory using the blackboard computations (one-dimensional cellular automata) as the standard computation model; we argue the benefits of such approach. This article is somewhat based on my series of talks from Warsztaty Logiczne 2014 in Białka Tatrzańska, although these talks covered more topics, such as NL=coNL, and links between BPP and the polynomial hierarchy.

Słowa kluczowe

EN

alternation; cellular automata; Savitch theorem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 152, nr 4
• Strony: 323--339
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Kopczyński E.

• Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland

Bibliografia

• [1] Harel D, Rosner R. Algorithmics: The Spirit of Computing. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2nd edition, 1992. ISBN 0201504014.
• [2] Arora S, Barak B. Computational Complexity: A Modern Approach. Cambridge University Press, New York, NY, USA, 1st edition, 2009. ISBN 0521424267, 9780521424264.
• [3] Papadimitriou CM. Computational complexity. Addison-Wesley, Reading, Massachusetts, 1994. ISBN 0201530821.
• [4] Niwiński D. Computational complexity, 2011-2016. URL https://www.mimuw.edu.pl/~niwinski/Zlozonosc/2016/2016.html (as of Feb 16, 2017).
• [5] Cook M. Universality in elementary cellular automata. Complex systems, 2004. 15(1):1–40.
• [6] Chandra AK, Kozen DC, Stockmeyer LJ. Alternation. J. ACM, 1981. 28(1):114–133. doi:10.1145/322234.322243. URL http://doi.acm.org/10.1145/322234.322243.
• [7] van Emde Boas P. Playing Savitch and Cooking Games, pp. 10–21. Springer Berlin Heidelberg, Berlin, Heidelberg. ISBN 978-3-642-11512-7, 2010. doi:10.1007/978-3-642-11512-7_2. URL http://dx.doi.org/10.1007/978-3-642-11512-7_2.
• [8] Shor PW. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, SFCS ’94. IEEE Computer Society, Washington, DC, USA. ISBN 0-8186-6580-7, 1994 pp. 124–134. doi:10.1109/SFCS.1994.365700. URL http://dx.doi.org/10.1109/SFCS.1994.365700.
• [9] Minsky ML. Computation: Finite and Infinite Machines. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1967. ISBN 0-13-165563-9.
• [10] Kaye P, Laflamme R, Mosca M. An Introduction to Quantum Computing. Oxford University Press, Inc., New York, NY, USA, 2007. ISBN 0198570007.
• [11] Agrawal M, Kayal N, Saxena N. PRIMES is in P. Annals of mathematics, 2004. pp. 781–793.
• [12] van Emde Boas P. Machine Models and Simulations. In: van Leeuwen J (ed.), Handbook of Theoretical Computer Science (Vol. A), pp. 1–66. MIT Press, Cambridge, MA, USA. ISBN 0-444-88071-2, 1990. URL http://dl.acm.org/citation.cfm?id=114872.114873.
• [13] Karp RM. Reducibility Among Combinatorial Problems. In: Miller and Thatcher [15], 1972 pp. 85–103. URL http://www.cs.berkeley.edu/~luca/cs172/karp.pdf.
• [14] Kaye R. Minesweeper is NP-complete. The Mathematical Intelligencer, 2000. 22(2):9–15.
• [15] Miller RE, Thatcher JW (eds.). Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, The IBM Research Symposia Series. Plenum Press, New York, 1972. ISBN 0-306-30707-3.