Theory of computation 2026 - История изменений

Spulari: /* Lectures and seminars */

2026-09-18T04:33:39Z

Lectures and seminars

← Предыдущая версия		Версия от 04:33, 18 сентября 2026
Строка 26:		Строка 26:
	\| 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.		\| 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/1dh-zh5jq7g0xTgjeftjw3cnRh4jVkBMO/view?usp=sharing Lecture notes]
	\|		\| [https://drive.google.com/file/d/1fa-U8JLTacMsfjM4d_koHIIkDxbDESzV/view?usp=sharing Seminar notes]

	\|-		\|-

Spulari: /* References */

2026-09-17T09:35:18Z

References

← Предыдущая версия		Версия от 09:35, 17 сентября 2026
Строка 130:		Строка 130:
	== References ==		== References ==

	* Sanjeev Arora and Boaz Barak, ''Computational Complexity: A Modern Approach''.		* 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, ''Introduction to the Theory of Computation''.		* Michael Sipser, ''[https://www.cengage.com/c/student/9781133187790/ Introduction to the Theory of Computation]'', 3rd edition, Cengage, 2013.

	== Evaluation scheme ==		== Evaluation scheme ==

Spulari: /* Lectures and seminars */

2026-09-17T09:33:48Z

Lectures and seminars

← Предыдущая версия		Версия от 09:33, 17 сентября 2026
Строка 4:		Строка 4:

	== Lectures and seminars ==		== Lectures and seminars ==

	{\| class="wikitable" style="width:100%;"		{\| class="wikitable" style="width:100%;"
	! style="width:4%;" \| No.		! style="width:4%;" \| No.
Строка 17:		Строка 16:
	\| 11 September		\| 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/1AmNOOyn4xKrCpmtWYbBj7Thk5HhZnQTb/view?usp=sharing Lecture notes]
	\| [https://drive.google.com/file/d/1t-eYK1s320IL0Ww6c7YypAXO1zDUEvGI/view?usp=sharing Seminar notes]		\| [https://drive.google.com/file/d/1t-eYK1s320IL0Ww6c7YypAXO1zDUEvGI/view?usp=sharing Seminar notes]
Строка 24:		Строка 23:
	\| 2		\| 2
	\| 18 September		\| 18 September
	\| '''~~Nondeterminism~~, NP, and ~~reductions~~'''		\| '''Resource bounds, nondeterminism, and NP'''
	\| Nondeterministic machines and polynomial-time verifiers; ~~proof~~ of ~~their equivalence~~. Polynomial-time many-one reductions, NP-hardness, and NP-completeness.		\| 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/1dh-zh5jq7g0xTgjeftjw3cnRh4jVkBMO/view?usp=sharing Lecture notes]
	\|		\|
Строка 108:		Строка 107:
	\|		\|
	\|		\|

	\|}		\|}

Spulari: /* Lectures and seminars */

2026-09-17T09:31:28Z

Lectures and seminars

← Предыдущая версия		Версия от 09:31, 17 сентября 2026
Строка 23:		Строка 23:
	\|-		\|-
	\| 2		\| 2
	\|		\| 18 September
	\| '''Nondeterminism, NP, and reductions'''		\| '''Nondeterminism, NP, and reductions'''
	\| Nondeterministic machines and polynomial-time verifiers; proof of their equivalence. Polynomial-time many-one reductions, NP-hardness, and NP-completeness.		\| Nondeterministic machines and polynomial-time verifiers; proof of their equivalence. Polynomial-time many-one reductions, NP-hardness, and NP-completeness.
	\|		\| [https://drive.google.com/file/d/1dh-zh5jq7g0xTgjeftjw3cnRh4jVkBMO/view?usp=sharing Lecture notes]
	\|		\|

Spulari: /* Theory of Computation */

2026-09-11T04:39:59Z

Theory of Computation

← Предыдущая версия		Версия от 04:39, 11 сентября 2026
Строка 19:		Строка 19:
	\| Multitape Turing machines and efficient universal simulation. Time and space complexity; DTIME, DSPACE, P, PSPACE, and EXP. Time- and space-constructible bounds.		\| Multitape Turing machines and efficient universal simulation. Time and space complexity; DTIME, DSPACE, P, PSPACE, and EXP. Time- and space-constructible bounds.
	\| [https://drive.google.com/file/d/1AmNOOyn4xKrCpmtWYbBj7Thk5HhZnQTb/view?usp=sharing Lecture notes]		\| [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]

	\|-		\|-

Spulari: /* Theory of Computation */

2026-09-10T20:55:44Z

Theory of Computation

← Предыдущая версия		Версия от 20:55, 10 сентября 2026
Строка 129:		Строка 129:
	\|		\|
	\|}		\|}

			== References ==

			* Sanjeev Arora and Boaz Barak, ''Computational Complexity: A Modern Approach''.
			* Michael Sipser, ''Introduction to the Theory of Computation''.

	== Evaluation scheme ==		== Evaluation scheme ==

Spulari: /* Theory of Computation */

2026-09-09T08:22:39Z

Theory of Computation

← Предыдущая версия		Версия от 08:22, 9 сентября 2026
Строка 18:		Строка 18:
	\| '''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 Turing machines and efficient universal simulation. Time and space complexity; DTIME, DSPACE, P, PSPACE, and EXP. Time- and space-constructible bounds.
	\|		\| [https://drive.google.com/file/d/1AmNOOyn4xKrCpmtWYbBj7Thk5HhZnQTb/view?usp=sharing Lecture notes]
	\|		\|

Spulari: /* Theory of Computation */

2026-09-09T07:54:32Z

Theory of Computation

@@ Строка 106: / Строка 106: @@
 | '''The Sipser–Gács–Lautemann theorem'''
 | Amplification to exponentially small error, translations of accepting random strings, and the covering lemma. Full proof that BPP ⊆ Σ₂ᴾ ∩ Π₂ᴾ.
+|
+|

Spulari: /* Theory of Computation */

2026-09-09T07:51:31Z

Theory of Computation

← Предыдущая версия		Версия от 07:51, 9 сентября 2026
Строка 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 ==

Spulari: /* Theory of Computation */

2026-09-09T07:49:13Z

Theory of Computation

← Предыдущая версия		Версия от 07:49, 9 сентября 2026
Строка 5:		Строка 5:
	{\| 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:		Строка 13:
	\|-		\|-
	\| 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 Turing machines and efficient universal simulation. Time and space complexity; DTIME, DSPACE, P, PSPACE, and EXP. Time- and space-constructible bounds.
Строка 19:		Строка 21:
	\|-		\|-
	\| 2		\| 2
			\|
	\| '''Nondeterminism, NP, and reductions'''		\| '''Nondeterminism, NP, and reductions'''
	\| Nondeterministic machines and polynomial-time verifiers; proof of their equivalence. Polynomial-time many-one reductions, NP-hardness, and NP-completeness.		\| Nondeterministic machines and polynomial-time verifiers; proof of their equivalence. Polynomial-time many-one reductions, NP-hardness, and NP-completeness.
Строка 26:		Строка 29:
	\|-		\|-
	\| 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:		Строка 37:
	\|-		\|-
	\| 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:		Строка 45:
	\|-		\|-
	\| 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:		Строка 53:
	\|-		\|-
	\| 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:		Строка 61:
	\|-		\|-
	\| 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:		Строка 69:
	\|-		\|-
	\| 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:		Строка 77:
	\|-		\|-
	\| 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:		Строка 85:
	\|-		\|-
	\| 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:		Строка 93:
	\|-		\|-
	\| 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:		Строка 101:
	\|-		\|-
	\| 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 ⊆ Σ₂ᴾ ∩ Π₂ᴾ.
Строка 96:		Строка 109:
	\|-		\|-
	\| 13		\| 13
			\|
	\| '''Communication complexity'''		\| '''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.		\| 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.
Строка 103:		Строка 117:
	\|-		\|-
	\| 14		\| 14
			\|
	\| '''Streaming algorithms and sketches'''		\| '''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.		\| 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:		Строка 130:
	! 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
			\|
	\|}		\|}