Theory of computation 2026: различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к навигации Перейти к поиску
← Предыдущая правкаСледующая правка →
Метка: очистка
Нет описания правки
Строка 1: Строка 1:
= Theory of Computation =


== Lecturers ==
{| class="wikitable"
! Role
! Lecturer
|-
| '''Lecturer'''
| '''Subin Pulari'''
|-
| '''Seminar lecturer'''
| '''Yaroslav Ivanashev'''
|}
== Evaluation policy ==
The course evaluation consists of two colloquia and two examinations:
* '''Colloquium 1'''
* '''Colloquium 2'''
* '''Midterm examination'''
* '''Final examination'''
The final grade is calculated as follows:
* '''Colloquia: 60%''' — average of the two colloquium grades.
* '''Examinations: 40%''' — average of the midterm and final examination grades.
Thus:
'''Final grade = 0.6 × (average colloquium grade) + 0.4 × (average examination grade).'''
== Lectures and seminars ==
{| class="wikitable" style="width:100%;"
! style="width:5%;" | Lecture
! style="width:59%;" | Contents
! style="width:18%;" | Lecture notes
! style="width:18%;" | Seminar notes
|-
| '''1'''
| '''Computational models and resource bounds.''' Multitape Turing machines; configurations; time and space complexity; DTIME and DSPACE; P, PSPACE, and EXP; machine-model robustness; efficient universal simulation in O(T log T) time; time- and space-constructible bounds.
| Lectures 1–4
| Seminars 1–4
|-
| '''2'''
| '''Nondeterminism, NP, and reductions.''' Nondeterministic computation; polynomial-time verifiers and certificates; equivalence of the two definitions of NP; polynomial-time many-one reductions; NP-hardness and NP-completeness; bounded nondeterministic machine acceptance.
| Lectures 1–4
| Seminars 1–4
|-
| '''3'''
| '''The Cook–Levin theorem.''' Computation tableaux; Boolean encoding of configurations; start, transition, and acceptance constraints; local consistency; the local-to-global argument; polynomial-size construction; SAT is NP-complete.
| Lectures 1–4
| Seminars 1–4
|-
| '''4'''
| '''Time and space hierarchy theorems.''' Diagonalization; padded machine descriptions; universal simulation; deterministic time hierarchy; deterministic space hierarchy; constructibility; strict separations between resource-bounded classes.
| Lectures 1–4
| Seminars 1–4
|-
| '''5'''
| '''Space complexity and Savitch's theorem.''' Configuration graphs; logarithmic space; directed s–t connectivity; log-space reductions; STCON is NL-complete; recursive reachability; Savitch's theorem NSPACE(s) ⊆ DSPACE(s²); NPSPACE = PSPACE.
| Lectures 5–8
| Seminars 5–8
|-
| '''6'''
| '''The Immerman–Szelepcsényi theorem.''' Nondeterministic space and complementation; reachability layers; inductive counting; certification of nonreachability; NL = coNL; closure of nondeterministic space under complement.
| Lectures 5–8
| Seminars 5–8
|-
| '''7'''
| '''PSPACE-completeness.''' Quantified Boolean formulas; recursive QBF evaluation; TQBF ∈ PSPACE; succinct configuration reachability; universal-selector compression; PSPACE-hardness of TQBF; games and succinct planning.
| Lectures 5–8
| Seminars 5–8
|-
| '''8'''
| '''Boolean circuits and nonuniformity.''' Boolean circuits; circuit size and depth; circuit families; P/poly; simulation of polynomial-time machines by polynomial-size circuits; nonuniform computation; polynomial advice; equivalence between polynomial advice and polynomial-size circuit families.
| Lectures 5–8
| Seminars 5–8
|-
| '''9'''
| '''Circuit size and parallel computation.''' Shannon's counting argument; existence and abundance of hard Boolean functions; uniformity; NC^k and AC^k; bounded-fan-in depth lower bounds; locality of NC^0; constant-depth circuits for binary addition.
| Lectures 9–12
| Seminars 9–12
|-
| '''10'''
| '''The polynomial hierarchy.''' Alternating quantified-predicate characterizations; Σ_k^P and Π_k^P; quantified-circuit complete problems; complementation; collapse of the polynomial hierarchy; PH ⊆ PSPACE.
| Lectures 9–12
| Seminars 9–12
|-
| '''11'''
| '''Randomized computation.''' Probabilistic Turing machines; RP, coRP, ZPP, and BPP; one-sided and two-sided error amplification; ZPP = RP ∩ coRP; Adleman's theorem BPP ⊆ P/poly.
| Lectures 9–12
| Seminars 9–12
|-
| '''12'''
| '''The Sipser–Gács–Lautemann theorem.''' Amplification to exponentially small error; dense and sparse accepting sets; translations of the Boolean cube; covering lemma and the probabilistic method; quantified covering characterization; BPP ⊆ Σ_2^P ∩ Π_2^P.
| Lectures 9–12
| Seminars 9–12
|-
| '''13'''
| '''Communication complexity.''' Deterministic two-party protocols; protocol trees and transcripts; communication matrices; combinatorial rectangles; rectangle lower bounds; deterministic complexity of EQUALITY; public-coin fingerprinting; one-way communication; the INDEX lower bound.
| Lectures 13–14
| Seminars 13–14
|-
| '''14'''
| '''Streaming algorithms and sketches.''' One-pass streaming and frequency vectors; point queries; pairwise-independent hashing; Count–Min Sketch; collision analysis and confidence amplification; fixed-query and simultaneous guarantees; sketch space complexity; communication reductions; INDEX-based streaming-space lower bounds.
| Lectures 13–14
| Seminars 13–14
|}

Версия от 13:04, 27 августа 2026

Theory of Computation

Lecturers

Role Lecturer
Lecturer Subin Pulari
Seminar lecturer Yaroslav Ivanashev

Evaluation policy

The course evaluation consists of two colloquia and two examinations:

  • Colloquium 1
  • Colloquium 2
  • Midterm examination
  • Final examination

The final grade is calculated as follows:

  • Colloquia: 60% — average of the two colloquium grades.
  • Examinations: 40% — average of the midterm and final examination grades.

Thus:

Final grade = 0.6 × (average colloquium grade) + 0.4 × (average examination grade).

Lectures and seminars

Lecture Contents Lecture notes Seminar notes
1 Computational models and resource bounds. Multitape Turing machines; configurations; time and space complexity; DTIME and DSPACE; P, PSPACE, and EXP; machine-model robustness; efficient universal simulation in O(T log T) time; time- and space-constructible bounds. Lectures 1–4 Seminars 1–4
2 Nondeterminism, NP, and reductions. Nondeterministic computation; polynomial-time verifiers and certificates; equivalence of the two definitions of NP; polynomial-time many-one reductions; NP-hardness and NP-completeness; bounded nondeterministic machine acceptance. Lectures 1–4 Seminars 1–4
3 The Cook–Levin theorem. Computation tableaux; Boolean encoding of configurations; start, transition, and acceptance constraints; local consistency; the local-to-global argument; polynomial-size construction; SAT is NP-complete. Lectures 1–4 Seminars 1–4
4 Time and space hierarchy theorems. Diagonalization; padded machine descriptions; universal simulation; deterministic time hierarchy; deterministic space hierarchy; constructibility; strict separations between resource-bounded classes. Lectures 1–4 Seminars 1–4
5 Space complexity and Savitch's theorem. Configuration graphs; logarithmic space; directed s–t connectivity; log-space reductions; STCON is NL-complete; recursive reachability; Savitch's theorem NSPACE(s) ⊆ DSPACE(s²); NPSPACE = PSPACE. Lectures 5–8 Seminars 5–8
6 The Immerman–Szelepcsényi theorem. Nondeterministic space and complementation; reachability layers; inductive counting; certification of nonreachability; NL = coNL; closure of nondeterministic space under complement. Lectures 5–8 Seminars 5–8
7 PSPACE-completeness. Quantified Boolean formulas; recursive QBF evaluation; TQBF ∈ PSPACE; succinct configuration reachability; universal-selector compression; PSPACE-hardness of TQBF; games and succinct planning. Lectures 5–8 Seminars 5–8
8 Boolean circuits and nonuniformity. Boolean circuits; circuit size and depth; circuit families; P/poly; simulation of polynomial-time machines by polynomial-size circuits; nonuniform computation; polynomial advice; equivalence between polynomial advice and polynomial-size circuit families. Lectures 5–8 Seminars 5–8
9 Circuit size and parallel computation. Shannon's counting argument; existence and abundance of hard Boolean functions; uniformity; NC^k and AC^k; bounded-fan-in depth lower bounds; locality of NC^0; constant-depth circuits for binary addition. Lectures 9–12 Seminars 9–12
10 The polynomial hierarchy. Alternating quantified-predicate characterizations; Σ_k^P and Π_k^P; quantified-circuit complete problems; complementation; collapse of the polynomial hierarchy; PH ⊆ PSPACE. Lectures 9–12 Seminars 9–12
11 Randomized computation. Probabilistic Turing machines; RP, coRP, ZPP, and BPP; one-sided and two-sided error amplification; ZPP = RP ∩ coRP; Adleman's theorem BPP ⊆ P/poly. Lectures 9–12 Seminars 9–12
12 The Sipser–Gács–Lautemann theorem. Amplification to exponentially small error; dense and sparse accepting sets; translations of the Boolean cube; covering lemma and the probabilistic method; quantified covering characterization; BPP ⊆ Σ_2^P ∩ Π_2^P. Lectures 9–12 Seminars 9–12
13 Communication complexity. Deterministic two-party protocols; protocol trees and transcripts; communication matrices; combinatorial rectangles; rectangle lower bounds; deterministic complexity of EQUALITY; public-coin fingerprinting; one-way communication; the INDEX lower bound. Lectures 13–14 Seminars 13–14
14 Streaming algorithms and sketches. One-pass streaming and frequency vectors; point queries; pairwise-independent hashing; Count–Min Sketch; collision analysis and confidence amplification; fixed-query and simultaneous guarantees; sketch space complexity; communication reductions; INDEX-based streaming-space lower bounds. Lectures 13–14 Seminars 13–14
Источник — https://wiki.cs.hse.ru/index.php?title=Theory_of_computation_2026&oldid=96944