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

Материал из Wiki - Факультет компьютерных наук
Перейти к навигации Перейти к поиску
Новая страница: «= Computational Complexity Theory = == Course overview == Computational complexity theory studies the resources required to solve computational problems and the fundamental limitations of efficient computation. The course develops the main models, techniques, and complexity classes used to reason rigorously about computational difficulty. The course begins with time and space as computational resources and develops the basic complexity classes and hierarc...»
 
 
(не показано 13 промежуточных версий этого же участника)
Строка 1: Строка 1:
= Computational Complexity Theory =
= Theory of Computation =


== Course overview ==
'''Class Telegram group:''' [https://t.me/+rzgHdid7QpY4NDY0 Join the class group]
 
Computational complexity theory studies the resources required to solve computational problems and the fundamental limitations of efficient computation. The course develops the main models, techniques, and complexity classes used to reason rigorously about computational difficulty.
 
The course begins with time and space as computational resources and develops the basic complexity classes and hierarchy theorems. It then studies nondeterminism, NP-completeness, space complexity, circuits and nonuniform computation, the polynomial hierarchy, and randomized computation. The final part introduces communication complexity and shows how communication lower bounds can be used to prove lower bounds for streaming algorithms.
 
A recurring theme of the course is the use of '''reductions, diagonalization, counting, configurations, probabilistic arguments, and structural characterizations''' to compare computational models and establish upper and lower bounds.
 
== Lecturers ==
 
{| class="wikitable"
! Role
! Lecturer
|-
| '''Course lecturer'''
| '''Subin Pulari'''
|-
| '''Seminar lecturer'''
| '''Yaroslav Ivanashev'''
|}
 
== Evaluation policy ==
 
The course has no homework component. Evaluation is based on two colloquia and two examinations.
 
* '''Colloquium 1''' – during the first half of the course
* '''Colloquium 2''' – during the second half of the course
* '''Midterm examination'''
* '''Final examination'''
 
Let
<math>C_1,C_2</math> denote the two colloquium grades and
<math>E_1,E_2</math> denote the two examination grades.
 
The final course grade is calculated as
 
:<math>
\mathrm{Final\ Grade}
=
0.6\left(\frac{C_1+C_2}{2}\right)
+
0.4\left(\frac{E_1+E_2}{2}\right).
</math>
 
Thus:
 
* '''60%''' of the final grade comes from the average of the two colloquia;
* '''40%''' comes from the average of the two examinations.


== 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:55%;" | Contents
! style="width:9%;" | Date
! style="width:20%;" | Lecture notes
! style="width:17%;" | Lecture
! style="width:20%;" | 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; <math>\mathrm{DTIME}</math> and <math>\mathrm{DSPACE}</math>; <math>\mathbf P</math>, <math>\mathbf{PSPACE}</math>, and <math>\mathbf{EXP}</math>; machine-model robustness; efficient universal simulation in <math>O(T\log T)</math> time; time- and space-constructible bounds.
| 11 September
| [[Media:Complexity_Lecture_Notes_L01-L04_FINAL_20260827.pdf|Lectures 1–4]]
| '''Computational models and resource bounds'''
| [[Media:Complexity_Seminar_Question_Bank_L01-L04_FINAL_20260827.pdf|Seminar 1–4]]
| 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 <math>\mathbf{NP}</math>; polynomial-time many-one reductions; NP-hardness and NP-completeness; bounded nondeterministic machine acceptance.
| 18 September
| [[Media:Complexity_Lecture_Notes_L01-L04_FINAL_20260827.pdf|Lectures 1–4]]
| '''Resource bounds, nondeterminism, and NP'''
| [[Media:Complexity_Seminar_Question_Bank_L01-L04_FINAL_20260827.pdf|Seminar 1–4]]
| 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.
|
| [[Media:Complexity_Lecture_Notes_L01-L04_FINAL_20260827.pdf|Lectures 1–4]]
| '''The Cook–Levin theorem'''
| [[Media:Complexity_Seminar_Question_Bank_L01-L04_FINAL_20260827.pdf|Seminar 1–4]]
| 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.
|
| [[Media:Complexity_Lecture_Notes_L01-L04_FINAL_20260827.pdf|Lectures 1–4]]
| '''Time and space hierarchy theorems'''
| [[Media:Complexity_Seminar_Question_Bank_L01-L04_FINAL_20260827.pdf|Seminar 1–4]]
| 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 <math>s</math>–<math>t</math> connectivity; log-space reductions; STCON is NL-complete; recursive reachability; Savitch's theorem <math>\mathrm{NSPACE}(s)\subseteq\mathrm{DSPACE}(s^2)</math>; <math>\mathbf{NPSPACE}=\mathbf{PSPACE}</math>.
|
| [[Media:Complexity_Lecture_Notes_L05-L08_FINAL_20260827.pdf|Lectures 5–8]]
| '''Space complexity and Savitch's theorem'''
| [[Media:Complexity_Seminar_Question_Bank_L05-L08_FINAL_20260827.pdf|Seminar 5–8]]
| 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; <math>\mathbf{NL}=\mathbf{coNL}</math>; closure of nondeterministic space under complement.
|
| [[Media:Complexity_Lecture_Notes_L05-L08_FINAL_20260827.pdf|Lectures 5–8]]
| '''The Immerman–Szelepcsényi theorem'''
| [[Media:Complexity_Seminar_Question_Bank_L05-L08_FINAL_20260827.pdf|Seminar 5–8]]
| 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; <math>\mathrm{TQBF}\in\mathbf{PSPACE}</math>; succinct configuration reachability; universal-selector compression; PSPACE-hardness of TQBF; games and succinct planning.
|
| [[Media:Complexity_Lecture_Notes_L05-L08_FINAL_20260827.pdf|Lectures 5–8]]
| '''PSPACE-completeness'''
| [[Media:Complexity_Seminar_Question_Bank_L05-L08_FINAL_20260827.pdf|Seminar 5–8]]
| 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; <math>\mathbf{P}/\mathrm{poly}</math>; simulation of polynomial-time machines by polynomial-size circuits; nonuniform computation; polynomial advice; equivalence between polynomial advice and polynomial-size circuit families.
|
| [[Media:Complexity_Lecture_Notes_L05-L08_FINAL_20260827.pdf|Lectures 5–8]]
| '''Boolean circuits and nonuniformity'''
| [[Media:Complexity_Seminar_Question_Bank_L05-L08_FINAL_20260827.pdf|Seminar 5–8]]
| 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; <math>\mathbf{NC}^k</math> and <math>\mathbf{AC}^k</math>; bounded-fan-in depth lower bounds; locality of <math>\mathbf{NC}^0</math>; constant-depth circuits for binary addition.
|
| [[Media:Complexity_Lecture_Notes_L09-L12_FINAL_20260827.pdf|Lectures 9–12]]
| '''Circuit size and parallel computation'''
| [[Media:Complexity_Seminar_Question_Bank_L09-L12_FINAL_20260827.pdf|Seminar 9–12]]
| 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; <math>\mathbf{\Sigma}_k^{\mathbf P}</math> and <math>\mathbf{\Pi}_k^{\mathbf P}</math>; quantified-circuit complete problems; complementation; collapse of the polynomial hierarchy; <math>\mathbf{PH}\subseteq\mathbf{PSPACE}</math>.
|
| [[Media:Complexity_Lecture_Notes_L09-L12_FINAL_20260827.pdf|Lectures 9–12]]
| '''The polynomial hierarchy'''
| [[Media:Complexity_Seminar_Question_Bank_L09-L12_FINAL_20260827.pdf|Seminar 9–12]]
| 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; <math>\mathbf{RP}</math>, <math>\mathbf{coRP}</math>, <math>\mathbf{ZPP}</math>, and <math>\mathbf{BPP}</math>; one-sided and two-sided error amplification; <math>\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}</math>; Adleman's theorem <math>\mathbf{BPP}\subseteq\mathbf{P}/\mathrm{poly}</math>.
|
| [[Media:Complexity_Lecture_Notes_L09-L12_FINAL_20260827.pdf|Lectures 9–12]]
| '''Randomized computation'''
| [[Media:Complexity_Seminar_Question_Bank_L09-L12_FINAL_20260827.pdf|Seminar 9–12]]
| 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; <math>\mathbf{BPP}\subseteq\mathbf{\Sigma}_2^{\mathbf P}\cap\mathbf{\Pi}_2^{\mathbf P}</math>.
|
| [[Media:Complexity_Lecture_Notes_L09-L12_FINAL_20260827.pdf|Lectures 9–12]]
| '''The Sipser–Gács–Lautemann theorem'''
| [[Media:Complexity_Seminar_Question_Bank_L09-L12_FINAL_20260827.pdf|Seminar 9–12]]
| Amplification to exponentially small error, translations of accepting random strings, and the covering lemma. Full proof that BPP ⊆ Σ₂ᴾ ∩ Π₂ᴾ.
|
|
|}
 
== Lecturers ==


{| class="wikitable"
! Role
! Lecturer
! Contact
! Office hours
|-
|-
| '''13'''
| '''Lecturer'''
| '''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.
| Subin Pulari
| [[Media:Complexity_Lecture_Notes_L13-L14_FINAL_20260827.pdf|Lectures 13–14]]
| Telegram: @spulari<br>Email: spulari@hse.ru
| [[Media:Complexity_Seminar_Question_Bank_L13-L14_FINAL_20260827.pdf|Seminar 13–14]]
| Monday–Friday, by appointment via Telegram or email
|-
| '''Seminar lecturer'''
| Yaroslav Ivanashev
| Telegram: @ivanashev
|
|}


|-
== References ==
| '''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.
* Sanjeev Arora and Boaz Barak, ''[https://www.cambridge.org/core/books/computational-complexity/3453CAFDEB0B4820B186FE69A64E1086 Computational Complexity: A Modern Approach]'', Cambridge University Press, 2009.
| [[Media:Complexity_Lecture_Notes_L13-L14_FINAL_20260827.pdf|Lectures 13–14]]
* Michael Sipser, ''[https://www.cengage.com/c/student/9781133187790/ Introduction to the Theory of Computation]'', 3rd edition, Cengage, 2013.
| [[Media:Complexity_Seminar_Question_Bank_L13-L14_FINAL_20260827.pdf|Seminar 13–14]]
 
== Evaluation scheme ==
 
The course has one '''midterm assessment''' and one '''end-term assessment'''. Each assessment consists of one colloquium and one written examination.
 
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
 
:<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>
 
The final course score is


|}
:<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