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

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


{| class="wikitable" style="width:100%;"
{| class="wikitable" style="width:100%;"
! style="width:5%;" | Lecture
! style="width:4%;" | No.
! style="width:59%;" | Contents
! style="width:18%;" | Lecture
! style="width:18%;" | Lecture notes
! style="width:52%;" | Contents and principal results
! style="width:18%;" | Seminar notes
! style="width:13%;" | Lecture notes
! style="width:13%;" | Seminar notes


|-
|-
| '''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 and efficient universal simulation. Time and space complexity; DTIME, DSPACE, P, PSPACE, and EXP. Time- and space-constructible bounds.
|
|
|
|


|-
|-
| '''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 machines and polynomial-time verifiers; proof of their equivalence. Polynomial-time many-one reductions, NP-hardness, and NP-completeness.
|
|
|
|


|-
|-
| '''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'''
| Tableau proof that Boolean satisfiability is NP-complete: encoding configurations, local transitions, the initial configuration, and acceptance.
|
|
|
|


|-
|-
| '''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 and universal simulation. Full proofs of the deterministic time hierarchy theorem and the deterministic space hierarchy theorem.
|
|
|
|


|-
|-
| '''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 and STCON as an NL-complete problem. Recursive reachability and the proof of NSPACE(s) ⊆ DSPACE(s²); in particular, NPSPACE = PSPACE.
|
|
|
|


|-
|-
| '''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'''
| Inductive counting of reachable configurations and the complete proof that nondeterministic space is closed under complement; in particular, NL = coNL.
|
|
|
|


|-
|-
| '''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 and recursive evaluation. Complete proof that TQBF is PSPACE-complete via polynomial-space configuration reachability; applications to games and planning.
|
|
|
|


|-
|-
| '''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'''
| Circuit families, size, and depth. Simulation of polynomial-time machines by polynomial-size circuits; P ⊆ P/poly and the characterization of P/poly by polynomial advice.
|
|
|
|


|-
|-
| '''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'''
| The counting lower bound for Boolean circuits. Uniformity; the classes AC and NC; elementary depth lower bounds, the locality of NC⁰, and a constant-depth construction for binary addition.
|
|
|
|


|-
|-
| '''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'''
| The classes Σₖᴾ and Πₖᴾ and their quantified-predicate characterizations. Complete quantified-circuit problems, collapse of the hierarchy, and PH ⊆ PSPACE.
|
|
|
|


|-
|-
| '''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 machines and the classes RP, coRP, ZPP, and BPP. Error amplification, ZPP = RP ∩ coRP, and the probabilistic proof that BPP ⊆ P/poly.
|
|
|
|


|-
|-
| '''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, translations of accepting random strings, and the covering lemma. Full proof that BPP ⊆ Σ₂ᴾ ∩ Π₂ᴾ.
|
|
|
|


|-
|-
| '''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 and public-coin protocols, protocol trees, and combinatorial rectangles. A linear deterministic lower bound for EQUALITY, a public-coin fingerprinting protocol for EQUALITY, and the deterministic one-way lower bound for INDEX.
|
|
|
|


|-
|-
| '''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'''
| The insertion-only frequency-vector model. Pairwise-independent hashing and Count–Min Sketch, with complete error and failure-probability analysis. A reduction from one-way INDEX proving a linear deterministic streaming-space lower bound for exact point queries.
|
|
|
|
Строка 102: Строка 117:
|-
|-
| '''Lecturer'''
| '''Lecturer'''
| '''Subin Pulari'''
| Subin Pulari
|-
|-
| '''Seminar lecturer'''
| '''Seminar lecturer'''
| '''Yaroslav Ivanashev'''
| Yaroslav Ivanashev
|}
|}


== Evaluation policy ==
== Evaluation scheme ==


The course evaluation consists of two colloquia and two examinations:
The course has one '''midterm assessment''' and one '''end-term assessment'''. Each assessment consists of one colloquium and one written examination.


* '''Colloquium 1'''
Let ''C<sub>mid</sub>'' and ''C<sub>end</sub>'' denote the two colloquium scores, and let ''E<sub>mid</sub>'' and ''E<sub>end</sub>'' denote the two examination scores. The aggregate scores are
* '''Colloquium 2'''
* '''Midterm examination'''
* '''Final examination'''


The final grade is calculated as follows:
:<big>'''C = (C<sub>mid</sub> + C<sub>end</sub>)/2, &nbsp;&nbsp;&nbsp; E = (E<sub>mid</sub> + E<sub>end</sub>)/2.'''</big>


* '''Colloquia: 60%''' — average of the two colloquium grades.
The final course score is
* '''Examinations: 40%''' — average of the midterm and final examination grades.


'''Final grade = 0.6 × (average colloquium grade) + 0.4 × (average examination grade).'''
:<big>'''Final score = 0.6 C + 0.4 E'''</big>

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

Theory of Computation

Lectures and seminars

No. Lecture Contents and principal results Lecture notes Seminar notes
1 Computational models and resource bounds Multitape Turing machines and efficient universal simulation. Time and space complexity; DTIME, DSPACE, P, PSPACE, and EXP. Time- and space-constructible bounds.
2 Nondeterminism, NP, and reductions Nondeterministic machines and polynomial-time verifiers; proof of their equivalence. Polynomial-time many-one reductions, NP-hardness, and NP-completeness.
3 The Cook–Levin theorem Tableau proof that Boolean satisfiability is NP-complete: encoding configurations, local transitions, the initial configuration, and acceptance.
4 Time and space hierarchy theorems Diagonalization and universal simulation. Full proofs of the deterministic time hierarchy theorem and the deterministic space hierarchy theorem.
5 Space complexity and Savitch's theorem Configuration graphs and STCON as an NL-complete problem. Recursive reachability and the proof of NSPACE(s) ⊆ DSPACE(s²); in particular, NPSPACE = PSPACE.
6 The Immerman–Szelepcsényi theorem Inductive counting of reachable configurations and the complete proof that nondeterministic space is closed under complement; in particular, NL = coNL.
7 PSPACE-completeness Quantified Boolean formulas and recursive evaluation. Complete proof that TQBF is PSPACE-complete via polynomial-space configuration reachability; applications to games and planning.
8 Boolean circuits and nonuniformity Circuit families, size, and depth. Simulation of polynomial-time machines by polynomial-size circuits; P ⊆ P/poly and the characterization of P/poly by polynomial advice.
9 Circuit size and parallel computation The counting lower bound for Boolean circuits. Uniformity; the classes AC and NC; elementary depth lower bounds, the locality of NC⁰, and a constant-depth construction for binary addition.
10 The polynomial hierarchy The classes Σₖᴾ and Πₖᴾ and their quantified-predicate characterizations. Complete quantified-circuit problems, collapse of the hierarchy, and PH ⊆ PSPACE.
11 Randomized computation Probabilistic machines and the classes RP, coRP, ZPP, and BPP. Error amplification, ZPP = RP ∩ coRP, and the probabilistic proof that BPP ⊆ P/poly.
12 The Sipser–Gács–Lautemann theorem Amplification to exponentially small error, translations of accepting random strings, and the covering lemma. Full proof that BPP ⊆ Σ₂ᴾ ∩ Π₂ᴾ.
13 Communication complexity Deterministic and public-coin protocols, protocol trees, and combinatorial rectangles. A linear deterministic lower bound for EQUALITY, a public-coin fingerprinting protocol for EQUALITY, and the deterministic one-way lower bound for INDEX.
14 Streaming algorithms and sketches The insertion-only frequency-vector model. Pairwise-independent hashing and Count–Min Sketch, with complete error and failure-probability analysis. A reduction from one-way INDEX proving a linear deterministic streaming-space lower bound for exact point queries.

Lecturers

Role Lecturer
Lecturer Subin Pulari
Seminar lecturer Yaroslav Ivanashev

Evaluation scheme

The course has one midterm assessment and one end-term assessment. Each assessment consists of one colloquium and one written examination.

Let Cmid and Cend denote the two colloquium scores, and let Emid and Eend denote the two examination scores. The aggregate scores are

C = (Cmid + Cend)/2,     E = (Emid + Eend)/2.

The final course score is

Final score = 0.6 C + 0.4 E
Источник — https://wiki.cs.hse.ru/index.php?title=Theory_of_computation_2026&oldid=96946