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

Материал из Wiki - Факультет компьютерных наук
Перейти к навигации Перейти к поиску
← Предыдущая правка
 
(не показано 10 промежуточных версий этого же участника)
Строка 1: Строка 1:
= Theory of Computation =
= Theory of Computation =
'''Class Telegram group:''' [https://t.me/+rzgHdid7QpY4NDY0 Join the class group]


== Lectures and seminars ==
== Lectures and seminars ==
{| class="wikitable" style="width:100%;"
{| class="wikitable" style="width:100%;"
! style="width:5%;" | Lecture
! style="width:4%;" | No.
! style="width:59%;" | Contents
! style="width:9%;" | Date
! style="width:18%;" | Lecture notes
! style="width:17%;" | Lecture
! style="width:18%;" | Seminar notes
! style="width:44%;" | Contents and principal results
! 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.
| 11 September
|
| '''Computational models and resource bounds'''
|
| Multitape deterministic Turing machines. Time complexity and the classes DTIME, P, and EXP. Space complexity and the classes DSPACE and PSPACE, with basic examples illustrating polynomial time and polynomial space.
| [https://drive.google.com/file/d/1AmNOOyn4xKrCpmtWYbBj7Thk5HhZnQTb/view?usp=sharing Lecture notes]
| [https://drive.google.com/file/d/1t-eYK1s320IL0Ww6c7YypAXO1zDUEvGI/view?usp=sharing Seminar notes]


|-
|-
| '''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.
| 18 September
|
| '''Resource bounds, nondeterminism, and NP'''
|
| Relations between time and space: DTIME(t) ⊆ DSPACE(t), P ⊆ PSPACE, and PSPACE ⊆ EXP. Simulation between Turing-machine models and universal computation. Nondeterministic Turing machines, NP, and polynomial-time verifiers; equivalence of the machine and verifier definitions. Polynomial-time many-one reductions, NP-hardness, and NP-completeness.
| [https://drive.google.com/file/d/1dh-zh5jq7g0xTgjeftjw3cnRh4jVkBMO/view?usp=sharing Lecture notes]
| [https://drive.google.com/file/d/1fa-U8JLTacMsfjM4d_koHIIkDxbDESzV/view?usp=sharing Seminar notes]


|-
|-
| '''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'''
| '''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'''
| 12
| '''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.
|
|
|
 
| '''The Sipser–Gács–Lautemann theorem'''
|-
| Amplification to exponentially small error, translations of accepting random strings, and the covering lemma. Full proof that BPP ⊆ Σ₂ᴾ ∩ Π₂ᴾ.
| '''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.
|
|
|
|
|}
|}


Строка 100: Строка 114:
! Role
! Role
! Lecturer
! Lecturer
! Contact
! Office hours
|-
|-
| '''Lecturer'''
| '''Lecturer'''
| '''Subin Pulari'''
| Subin Pulari
| Telegram: @spulari<br>Email: spulari@hse.ru
| Monday–Friday, by appointment via Telegram or email
|-
|-
| '''Seminar lecturer'''
| '''Seminar lecturer'''
| '''Yaroslav Ivanashev'''
| Yaroslav Ivanashev
| Telegram: @ivanashev
|
|}
|}


== Evaluation policy ==
== References ==
 
* Sanjeev Arora and Boaz Barak, ''[https://www.cambridge.org/core/books/computational-complexity/3453CAFDEB0B4820B186FE69A64E1086 Computational Complexity: A Modern Approach]'', Cambridge University Press, 2009.
* Michael Sipser, ''[https://www.cengage.com/c/student/9781133187790/ Introduction to the Theory of Computation]'', 3rd edition, Cengage, 2013.
 
== 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>

Текущая версия от 04:33, 18 сентября 2026

Theory of Computation

Class Telegram group: Join the class group

Lectures and seminars

No. Date Lecture Contents and principal results Lecture notes Seminar notes
1 11 September Computational models and resource bounds Multitape deterministic Turing machines. Time complexity and the classes DTIME, P, and EXP. Space complexity and the classes DSPACE and PSPACE, with basic examples illustrating polynomial time and polynomial space. Lecture notes Seminar notes
2 18 September Resource bounds, nondeterminism, and NP Relations between time and space: DTIME(t) ⊆ DSPACE(t), P ⊆ PSPACE, and PSPACE ⊆ EXP. Simulation between Turing-machine models and universal computation. Nondeterministic Turing machines, NP, and polynomial-time verifiers; equivalence of the machine and verifier definitions. Polynomial-time many-one reductions, NP-hardness, and NP-completeness. Lecture notes Seminar notes
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 ⊆ Σ₂ᴾ ∩ Π₂ᴾ.

Lecturers

Role Lecturer Contact Office hours
Lecturer Subin Pulari Telegram: @spulari
Email: spulari@hse.ru 		Monday–Friday, by appointment via Telegram or email
Seminar lecturer Yaroslav Ivanashev Telegram: @ivanashev

References

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=97671