Lecture notes a knihy

• Allenderovy lecture notes (http://athos.rutgers.edu/~allender/lecture.notes/ ) asi nejlepe pokryvaji to, co budeme probirat.
• Neco se da najit take v Goldreichovych poznamkach (http://www.wisdom.weizmann.ac.il/~oded/cc.html ).
• Základní pojmy jsou v různém rozsahu vyloženy např. v těchto knihách:
  Papadimitriou: Computational Complexity
  Garey, Johnson: Computers and Intractability. A guide to the theory of NP-completeness.
  

Probraná literatura a příslušné články a jiné zdroje

• Booleovské a algebraické obvody a jejich třídy. Definice a základní odhady velikosti (Shannon)
  
  • Wegenerova kniha The Complexity of Boolean functions je ke stažení na
    http://ls2-www.cs.uni-dortmund.de/monographs/bluebook/index.shtml.en
    
• Dolní odhady na velikost obvodů konstantní hloubky, Hastadovo "switching lemma".
  
  • Allenderovy poznamky, hezčí důkaz switching lemmatu je v článku
    Paul Beame. A switching lemma primer. Technical Report UW-CSE-95-07-01, Department of Computer Science and Engineering, University of Washington, November 1994. Ke stažení na http://www.cs.washington.edu/homes/beame/papers/primer.ps
    
• Obvody konstantní hloubky s prvky počítajícími paritu. Exponenciální dolní odhady (Razborov-Smolensky)
  
  • Allenderovy poznámky, příp. Wegenerova kniha.
    
• Exponenciální dolní odhady na velikost monotónních obvodů. Aproximační metoda.
  Je mnoho různých důkazů, Berg-Ulfberg nejbližší přednášenému. Haken-Cook a Pudlak maji zobecnění pro reálné obvody.
  
  • Ravi B. Boppana, Michael Sipser: The Complexity of Finite Functions. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990: 757-804
    
  • Armin Haken: Counting Bottlenecks to Show Monotone P <=> NP. FOCS 1995: 36-40.
  • Armin Haken, Stephen A. Cook: An Exponential Lower Bound for the Size of Monotone Real Circuits. JCSS 58(2): 326-335 (1999)
  • Pudlak P.: Lower bounds for resolution and cutting planes proofs and monotone computations, J. of Symb. Logic 62(3), 1997, pp.981-998.
    Ke stažení na http://www.math.cas.cz/~pudlak/interpol.ps
    
  • Christer Berg, Staffan Ulfberg: Symmetric Approximation Arguments for Monotone Lower Bounds Without Sunflowers. Computational Complexity 8(1): 1-20 (1999)
    
• Obvody konstantní hloubky s prvky počítajícími paritu a prahové funkce. Exponenciální dolní odhad pro hloubku 2 s obecnými vahami.
  
  • Hajnal A. Maass W. Pudlak P. Szegedy M. Turan G.: Threshold circuits of bounded depth. Journ. of Comput. and System Science 46 (1993), pp.129-154.
  • alternativní důkaz pomocí komunikační složitosti je v knize Kushilevitz, Nisan: Communication complexity.
    
• Výrokové počty, definice a souvislost se složitostí výpočtů.
  Dolní odhady pro vybrané výrokové kalkuly (interpolace). Algebraické systémy, základní vztahy k rezoluci.
  
  • Interpolace a její použití pro odhady v rezoluci a v cutting planes je v článku
    Pudlak P.: Lower bounds for resolution and cutting planes proofs and monotone computations, J. of Symb. Logic 62(3), 1997, pp.981-998.
    Ke stažení na http://www.math.cas.cz/~pudlak/interpol.ps
    
• Komunikační složitost jako metoda pro dokazování dolních odhadů.
  Základní pojmy, vztah deterministické a nedeterministické složitosti. Odhady na hloubku monotónních obvodů.
  Komunikační složitost s více hráči, její souvislosti s Booleovskými obvody (Valiantovo lemma, ACC obvody).
  
  • Kinha Kushilevitz, Nisan: Communication complexity.
  • Převod ACC obvodů na kvazipolynomiální obvody hloubky 3 je v Allenderových poznámkách, originál v článku
    R. Beigel and J. Tarui. On ACC. Computational Complexity, 4, 350-366, 1994. Special issue devoted to the 4th Annual McGill Workshop on Complexity Theory. Ke stažení na http://www.cis.temple.edu/~beigel/papers/bt-acc-cc.html
    
• Dolní odhady na velikost a hloubku formulí (nemonotónních)
  Krapčenkův odhad.
  
  • Kinha Kushilevitz, Nisan: Communication complexity. V původnější verzi Wegenerova kniha.
• Branching programy
  Definice, souvislost s Turingovými stroji, exponenciální dolní odhady pro read-once BP, omezena šířka počítá NC^1.
  
  • Wegenerova kniha