Computational Complexity on the Blackboard

Article type: Research Article

Authors: Kopczyński, Eryk^*

Affiliations: Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland. [email protected]

Correspondence: [*] Address for correspondence: University of Warsaw, Banacha 2, 02-097 Warszawa, Poland.

Abstract: 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.

Keywords: cellular automata, alternation, Savitch theorem

DOI: 10.3233/FI-2017-1523

Journal: Fundamenta Informaticae, vol. 152, no. 4, pp. 323-339, 2017