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

Материал из Wiki - Факультет компьютерных наук
Перейти к навигации Перейти к поиску
← Предыдущая правкаСледующая правка →
Нет описания правки
Строка 1: Строка 1:
= Theory of Computation =
= 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 ==
== Lectures and seminars ==
Строка 43: Строка 12:
| '''1'''
| '''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.
| '''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'''
| '''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.
| '''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'''
| '''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.
| '''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'''
| '''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.
| '''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'''
| '''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.
| '''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'''
| '''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.
| '''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'''
| '''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.
| '''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'''
| '''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.
| '''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'''
| '''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.
| '''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'''
| '''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.
| '''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'''
| '''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.
| '''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'''
| '''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.
| '''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'''
| '''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.
| '''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'''
| '''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.
| '''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
|


|}
|}
== 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.
'''Final grade = 0.6 × (average colloquium grade) + 0.4 × (average examination grade).'''

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

Theory of Computation

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

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.

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

Источник — https://wiki.cs.hse.ru/index.php?title=Theory_of_computation_2026&oldid=96945