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

Материал из Wiki - Факультет компьютерных наук
Перейти к навигации Перейти к поиску
← Предыдущая правка
 
(не показано 9 промежуточных версий этого же участника)
Строка 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:4%;" | No.
! style="width:4%;" | No.
! style="width:18%;" | Lecture
! style="width:9%;" | Date
! style="width:52%;" | Contents and principal results
! style="width:17%;" | Lecture
! style="width:44%;" | Contents and principal results
! style="width:13%;" | Lecture notes
! style="width:13%;" | Lecture notes
! style="width:13%;" | Seminar notes
! style="width:13%;" | Seminar notes
Строка 12: Строка 14:
|-
|-
| 1
| 1
| 11 September
| '''Computational models and resource 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.
| 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'''
| 18 September
| Nondeterministic machines and polynomial-time verifiers; proof of their equivalence. Polynomial-time many-one reductions, NP-hardness, and NP-completeness.
| '''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'''
| '''The Cook–Levin theorem'''
| Tableau proof that Boolean satisfiability is NP-complete: encoding configurations, local transitions, the initial configuration, and acceptance.
| Tableau proof that Boolean satisfiability is NP-complete: encoding configurations, local transitions, the initial configuration, and acceptance.
Строка 33: Строка 38:
|-
|-
| 4
| 4
|
| '''Time and space hierarchy theorems'''
| '''Time and space hierarchy theorems'''
| Diagonalization and universal simulation. Full proofs of the deterministic time hierarchy theorem and the deterministic space hierarchy theorem.
| Diagonalization and universal simulation. Full proofs of the deterministic time hierarchy theorem and the deterministic space hierarchy theorem.
Строка 40: Строка 46:
|-
|-
| 5
| 5
|
| '''Space complexity and Savitch's theorem'''
| '''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.
| Configuration graphs and STCON as an NL-complete problem. Recursive reachability and the proof of NSPACE(s) ⊆ DSPACE(s²); in particular, NPSPACE = PSPACE.
Строка 47: Строка 54:
|-
|-
| 6
| 6
|
| '''The Immerman–Szelepcsényi theorem'''
| '''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.
| Inductive counting of reachable configurations and the complete proof that nondeterministic space is closed under complement; in particular, NL = coNL.
Строка 54: Строка 62:
|-
|-
| 7
| 7
|
| '''PSPACE-completeness'''
| '''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.
| Quantified Boolean formulas and recursive evaluation. Complete proof that TQBF is PSPACE-complete via polynomial-space configuration reachability; applications to games and planning.
Строка 61: Строка 70:
|-
|-
| 8
| 8
|
| '''Boolean circuits and nonuniformity'''
| '''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.
| 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.
Строка 68: Строка 78:
|-
|-
| 9
| 9
|
| '''Circuit size and parallel computation'''
| '''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.
| 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.
Строка 75: Строка 86:
|-
|-
| 10
| 10
|
| '''The polynomial hierarchy'''
| '''The polynomial hierarchy'''
| The classes Σₖᴾ and Πₖᴾ and their quantified-predicate characterizations. Complete quantified-circuit problems, collapse of the hierarchy, and PH ⊆ PSPACE.
| The classes Σₖᴾ and Πₖᴾ and their quantified-predicate characterizations. Complete quantified-circuit problems, collapse of the hierarchy, and PH ⊆ PSPACE.
Строка 82: Строка 94:
|-
|-
| 11
| 11
|
| '''Randomized computation'''
| '''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.
| Probabilistic machines and the classes RP, coRP, ZPP, and BPP. Error amplification, ZPP = RP ∩ coRP, and the probabilistic proof that BPP ⊆ P/poly.
Строка 89: Строка 102:
|-
|-
| 12
| 12
|
| '''The Sipser–Gács–Lautemann theorem'''
| '''The Sipser–Gács–Lautemann theorem'''
| Amplification to exponentially small error, translations of accepting random strings, and the covering lemma. Full proof that BPP ⊆ Σ₂ᴾ ∩ Π₂ᴾ.
| 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.
|
|
|}
|}


Строка 115: Строка 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
|
|}
|}
== 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 ==
== Evaluation scheme ==

Текущая версия от 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