{{template>template:przedmiot|tytul=Złożoność obliczeniowa|prowadzacy=Krzysztof Loryś    |ects=6|typ=informatyczny.I2 (zaawansowany)}}
====== Złożoność obliczeniowa ======

===== Materiały =====
  * Podstawy obliczeń na TMs (Redukcja taśm dla (D,N.A) TM, Speed-up, etc.)
    * [2] Chapter 10
  * Podstawowe relacje między klasami obliczeń (hierarchia czasowa/ pamięciowa; obliczenia det/net/alt
  * Diagonalizacja
    * [1] Chapter 3
  * Lemat translacyjny
    * [[http://blog.computationalcomplexity.org/2005/04/translation-lemma.html|Computational Complexity: The Transaction Lemma]]
  * Hierarchia wielomianowa
    * [1] Chapter 5
  * Dolne ograniczenie na pamięć na rozpoznawanie języków nieregularnych
    * [3]
  * Twierdzenie (Immelman, Szelepcsenyi) Zamkniętość $NSPACE$ na dopełnienie
    * [[http://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem|Immerman–Szelepcsényi theorem]]
  * Twierdzenie (Mahaney): Konsekwencja istnienia $NP$-zupełnego zbioru rzadkiego
    * [[http://www.wisdom.weizmann.ac.il/~oded/CC/mahaney.pdf|Mahaney's Theorem]]
  * Twierdzenie (Hopcroft, Paul, Valiant): $DTIME(t) \subseteq DSPACE(t/log t)$
    * [4]
  * Twierdzenie (Weigel): Zamkniętość $PP$ na przecięcie
    * [5]
  * Twierdzenie (Valiant): Permanent jest $\#P$ zupełny
    * [1] 9.2
  * Twierdzenie (Paul, Pippenger, Szemeredi, Trotter): $DTIME(n) \subset NTIME(n)$
  * Twierdzenie (Toda) $PH \subseteq P^{\#SAT}$
    * [1] 9.3
  * Twierdzenie (Shamir): $IP = PSPACE$
    * [1] 8.5
  * Podstawy $PCP$
    * [1] 18

  * Licznik Furera: $DTIME_k(f) \subset DTIME_k(g)$ dla $f = o(g), k \geq 2$
    * {{:zlozonosc_obliczeniowa:furer.pdf|The tight deterministic time hierarchy}}

===== References =====
  - [[http://www.cs.princeton.edu/theory/complexity/book.pdf|Computational Complexity: A Modern Approach]] (draft)
  - Hopcroft, Ullman, Formal languages and their relation to automata, 1969
  - Lewis, Stearns, hartmanis, Memory bounds for recognition of context-free and context-sensitive languages, 1965
  - Hopcroft, Paul, Valiant, On Time vs Space
  - Beigel, Reingold, Spielman, PP is closed under intersetction
  - [[http://users.eecs.northwestern.edu/~fortnow/classes/f10/395-Complexity/Lecture3.pdf|Mahaney’s Theorem]]

{{tag>przedmioty_informatyczne zima_2010}}