Skripta obsahují většinu látky ze Složitosti II.

Errata

Errata jsou vztažena k verzi 1.1.

Faktické chyby

  • str. 17, důkaz věty 15, poslední odstavec: místo "potom L ∈ L(M￾)" má být "w ∈ L(M￾)" (David Majda)

  • str. 19, věta 18 b'): místo "NSPACE" má být nejspíš "DSPACE" (David Majda)

  • str. 20, důkaz věty 19: pozice pracovní hlavy není omezena log<sub>2</sub>n, ale log<sub>2</sub>S(n) (David Majda)

  • str. 20, důkaz věty 19, poslední odstavec: místo "V každý okamžik je na zásobníku O(S(n)) záznamů." má být "V každý okamžik je na zásobníku nejvýše O(S(n)) záznamů." (David Majda)

Překlepy, formátování apod.

  • str. 2, definice turingova stroje: místo "poh" má být "pod" (David Majda)

  • str. 3, definice přijímaného jayzka: za svislítkem je 2× "w" (David Majda)

  • str. 10, důkaz věty 9: v první větě má být místo "teda" slovo "tedy" (David Majda)