Theory of computation 2025 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Brbauwens (обсуждение | вклад) |
Brbauwens (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Seminars: After the lecture in room TBA and on the same zoomlink by [https://www.hse.ru/en/org/persons/190890122 Yaroslav Ivanashev] | Seminars: After the lecture in room TBA and on the same zoomlink by [https://www.hse.ru/en/org/persons/190890122 Yaroslav Ivanashev] | ||
| − | Telegram group for announcements and discussions [https://t.me/+7BOrITRebjk5MTc0 invite link.] The course is similar to [http://wiki.cs.hse.ru/ | + | Telegram group for announcements and discussions [https://t.me/+7BOrITRebjk5MTc0 invite link.] The course is similar to [http://wiki.cs.hse.ru/Theory_of_computation_2024 last year's one]. |
= Homeworks = | = Homeworks = | ||
| − | Deadlines: every 2 weeks, before the lecture | + | Deadlines: every 2 weeks, before the lecture. Submit in pdf or fotos of handwritten text in google classrooms. |
Tasks are in the problem lists from the seminar. Deadlines: problem lists 1 and 2: at the start of 3rd lecture, lists 3 and 4 at the start of the 5th lecture, etc. | Tasks are in the problem lists from the seminar. Deadlines: problem lists 1 and 2: at the start of 3rd lecture, lists 3 and 4 at the start of the 5th lecture, etc. | ||
| Строка 30: | Строка 30: | ||
! Rec !! Summary !! Problem list | ! Rec !! Summary !! Problem list | ||
|- | |- | ||
| − | || [https://www.youtube.com/watch?v=-VIr385nKVk | + | || [https://www.youtube.com/watch?v=-VIr385nKVk ??.09] || Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. [https://drive.google.com/file/d/15yDi0vZVVAw-2UuBu5Mxc17KWLzSIFML/view?usp=sharing Notes]|| [https://drive.google.com/file/d/19T2NKv8gWpLyYQtittxr9lzISdlIJguN/view?usp=sharing problem list 1] |
|- | |- | ||
|- | |- | ||
| − | || [https://www.youtube.com/watch?v=tnq5BkcGfk0 | + | || [https://www.youtube.com/watch?v=tnq5BkcGfk0 ??.09] || Simulating k-tape Turing on 1-tape. Undecidability of the Halting problem. Time and space hierarchy theorems. [https://drive.google.com/file/d/15yDi0vZVVAw-2UuBu5Mxc17KWLzSIFML/view?usp=sharing Notes] || [https://drive.google.com/file/d/1vX4cQ9nYWsetLQnZyFxTxzHQaTgJ62WL/view?usp=drive_link problem list 2] ''Update 02.10'' |
|- | |- | ||
| − | || [https://www.youtube.com/watch?v=VR_A62kFXH8 | + | || [https://www.youtube.com/watch?v=VR_A62kFXH8 ??.10] || Complexity class NP. Examples. Non-deterministic machines and another definition of NP. Polynomial reductions. NP-hardness and NP-completeness. || [https://drive.google.com/file/d/1SJq-s80aGYKBEtF84fz6pMYQM2ZE1UyA/view?usp=sharing problem list 3] |
|- | |- | ||
| − | || [https://www.youtube.com/watch?v=sGfulQ1YoUU | + | || [https://www.youtube.com/watch?v=sGfulQ1YoUU ??.10] || NP-completenes of NAE-3SAT, 3colorability, subsetsum, knapsack, Hamiltonian cycle. Circuits: examples, class P/poly, all functions have exponential circuits. https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&dl=0 circuit_notes.pdf] || [https://drive.google.com/file/d/1KtVCvyhO99T5cU_jYLG62Zwnqj5aDCor/view?usp=sharing problem list 4] |
|- | |- | ||
| − | || [https://www.youtube.com/watch?v=Jqy89FPbFj4 | + | || [https://www.youtube.com/watch?v=Jqy89FPbFj4 ??.10] || Circuit complexity. Classes AC^i and NC^i. Some functions have exponential circuit complexity. NC1 = Boolean formulas of polynomial size. Addition in AC0. Multiplication is in NC1. P is in P/poly. 3SAT is NP-complete. [https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&dl=0 circuit_notes.pdf] || [https://drive.google.com/file/d/15uGUYwI2GfNaEi0upjgjCqmclrWUk75c/view?usp=sharing problem list 5] |
|- | |- | ||
| − | || [https://youtube.com/live/kV86JYY8QXs | + | || [https://youtube.com/live/kV86JYY8QXs ??.10] || Directed Reachability is in SPACE(log^2 n). TQBF problem, its PSPACE-completeness. PSPACE = NPSPACE. NSPACE(s(n)) is in SPACE(s(n)^2) for space constructible s.|| [https://drive.google.com/file/d/1-vKS0TEAD05ol2BbFpbN510TbKhucBiw/view?usp=sharing problem list 6] |
|- | |- | ||
| − | || [https://youtube.com/live/W_uZuQXm53c | + | || [https://youtube.com/live/W_uZuQXm53c ??.11] || Oracle computation definitions. There exists an oracle ''A'' for which P<sup>''A''</sup> = NP<sup>''A''</sup>. There is an oracle B such that P<sup>''B''</sup> is not equal to NP<sup>''B''</sup>. || [https://drive.google.com/file/d/1T9mp2AuPV2YOQ0juTMd9g0VjczHvdnSB/view?usp=sharing problem list 7] |
|- | |- | ||
| − | || [https://youtube.com/live/ALO6r52wuIU | + | || [https://youtube.com/live/ALO6r52wuIU ??.11] || Probabilistic computation. Probabilistic machines, the class BPP, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. BPP is in P/poly. Most of it is also [https://www.youtube.com/watch?v=YSMgVbOqB-8&list=PLm3J0oaFux3YL5vLXpzOyJiLtqLp6dCW2&index=23 here] and [https://www.cs.cmu.edu/afs/cs/academic/class/15859-f04/www/scribes/lec2.pdf scribe1] [https://lucatrevisan.github.io/cs278-04/notes/lecture08.pdf scribe2] || [https://drive.google.com/file/d/1RlrxybN_p9X1WswJet9jpp9jPQLDYdpy/view?usp=sharing problem list 8] |
|- | |- | ||
| − | || [https://www.youtube.com/watch?v=X67F8P0dcAA | + | || [https://www.youtube.com/watch?v=X67F8P0dcAA ??.11] || Approximation algorithms. Definition c-approximation algorithm. 2-approximation for vertex cover and greedy vertex cover is not optimal. (ln n + 1)-approximation for set cover. PTAS for the makespan problem. Based on [https://www.youtube.com/watch?v=MEz1J9wY2iM&pp=ygUYYXBwcm94aW1hdGlvbiBhbGdvcml0aG1z MIT lecture].|| |
[https://drive.google.com/file/d/13hfO-2KUxpMnk8o0aLsJ8xO9IYfLzCHK/view?usp=sharing problem list 9] | [https://drive.google.com/file/d/13hfO-2KUxpMnk8o0aLsJ8xO9IYfLzCHK/view?usp=sharing problem list 9] | ||
|- | |- | ||
| − | || [https://youtube.com/live/r9rP3ZojeqY | + | || [https://youtube.com/live/r9rP3ZojeqY ??.11] || Parameterized complexity: The classes FPT and XP. Kernelization. Examples for vertex cover. [https://drive.google.com/file/d/1W9SU24HW0r5QhugzmrghpkzJUFuC8whq/view?usp=sharing Notes.] || [https://drive.google.com/file/d/1PpRK72BtyKYR0KVi03HDCy7HXvWpzcL6/view?usp=sharing problem list 10] <!-- [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&dl=0 programming task.] --> |
|- | |- | ||
| − | || [https://youtube.com/live/E4aNlvbYoLQ | + | || [https://youtube.com/live/E4aNlvbYoLQ ??.12] || Parameterized complexity: W-hierarchy, hardness from the exponential time hypothesis. [https://drive.google.com/file/d/1f-085Gr7E01HepUR-brGJDet-fXJzUwb/view?usp=sharing presentation] [https://drive.google.com/file/d/1OIw7h31N2tt-npC0NrvVgNhYGw_HlJa_/view?usp=sharing Notes] || [https://drive.google.com/file/d/1xhUYMsj0iV2TMZfR8FtkxWUNlcCjdS-N/view?usp=sharing problem list 11] ''Update 05.12'' |
|- | |- | ||
|| 11.12 || ''Colloquium.'' [https://drive.google.com/file/d/1no8CbHKJluGRx7FROpSS7BqXdjOVgdT1/view?usp=sharing Rules and questions.] Version Dec 8th. [https://docs.google.com/spreadsheets/d/10zH6TVcdXWrecW8jcl57MIIq-a_Osk3-bKtPXzQIzA0/edit?usp=sharing Shedule.] || [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam] | || 11.12 || ''Colloquium.'' [https://drive.google.com/file/d/1no8CbHKJluGRx7FROpSS7BqXdjOVgdT1/view?usp=sharing Rules and questions.] Version Dec 8th. [https://docs.google.com/spreadsheets/d/10zH6TVcdXWrecW8jcl57MIIq-a_Osk3-bKtPXzQIzA0/edit?usp=sharing Shedule.] || [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam] | ||
| Строка 77: | Строка 77: | ||
= Exam = | = Exam = | ||
| − | |||
| − | |||
5 or 6 questions with the same difficulty as the homework questions. You have 3 hours time. | 5 or 6 questions with the same difficulty as the homework questions. You have 3 hours time. | ||
| Строка 123: | Строка 121: | ||
Final score = 0.35 * [score homework] + 0.35 * [score colloquium] + 0.3 * [score exam] <br> | Final score = 0.35 * [score homework] + 0.35 * [score colloquium] + 0.3 * [score exam] <br> | ||
| − | For PI students (the course is called "computational complexity" and takes 3 modules). There are 2 scores for this course. The first one, given in December is calculated by the above formula (but it does not mean anything). The second score is given below, and it is the one that will be in the diploma. It includes a programming project. The assignment and grader, will be set up by the end of Februari, the deadline is the end of March. | + | <!-- For PI students (the course is called "computational complexity" and takes 3 modules). There are 2 scores for this course. The first one, given in December is calculated by the above formula (but it does not mean anything). The second score is given below, and it is the one that will be in the diploma. It includes a programming project. The assignment and grader, will be set up by the end of Februari, the deadline is the end of March. |
Final score = 0.3 * [score homework] + 0.3 * [score colloquium] + 0.2 * [score exam] + 0.2 * [score project] <br> | Final score = 0.3 * [score homework] + 0.3 * [score colloquium] + 0.2 * [score exam] + 0.2 * [score project] <br> | ||
| − | + | --> | |
Some homework assignments contain extra problems. Each solution of an extra problem will give 0.5 extra points on the final exam (which is graded out of 10). There will be around 10 extra problems. Rounding is applied only when the final score is transferred to the official grade. Arithmetic rounding is used. Autogrades. If only 6/10 for the exam is needed to get a final score of 10/10, then this will be given automatically. | Some homework assignments contain extra problems. Each solution of an extra problem will give 0.5 extra points on the final exam (which is graded out of 10). There will be around 10 extra problems. Rounding is applied only when the final score is transferred to the official grade. Arithmetic rounding is used. Autogrades. If only 6/10 for the exam is needed to get a final score of 10/10, then this will be given automatically. | ||
| Строка 133: | Строка 131: | ||
= Office hours = | = Office hours = | ||
| − | Bruno Bauwens: | + | Bruno Bauwens: TBA |
| − | + | Subin Pulari: TBA | |
Версия 20:04, 15 сентября 2025
Содержание
Classes
Lectures: time TBA in Pokrovkaya room TBA and in zoom by Bruno Bauwens.
Seminars: After the lecture in room TBA and on the same zoomlink by Yaroslav Ivanashev
Telegram group for announcements and discussions invite link. The course is similar to last year's one.
Homeworks
Deadlines: every 2 weeks, before the lecture. Submit in pdf or fotos of handwritten text in google classrooms.
Tasks are in the problem lists from the seminar. Deadlines: problem lists 1 and 2: at the start of 3rd lecture, lists 3 and 4 at the start of the 5th lecture, etc.
Late policy: 1 homework can be submitted at most 24h late without explanations.
Course Materials
The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 4, 7–9.
If you need some background in math, consider: Lecture notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi and Лекции по дискретной математике (черновик учебника, in Russian)
| Rec | Summary | Problem list |
|---|---|---|
| ??.09 | Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. Notes | problem list 1 |
| ??.09 | Simulating k-tape Turing on 1-tape. Undecidability of the Halting problem. Time and space hierarchy theorems. Notes | problem list 2 Update 02.10 |
| ??.10 | Complexity class NP. Examples. Non-deterministic machines and another definition of NP. Polynomial reductions. NP-hardness and NP-completeness. | problem list 3 |
| ??.10 | NP-completenes of NAE-3SAT, 3colorability, subsetsum, knapsack, Hamiltonian cycle. Circuits: examples, class P/poly, all functions have exponential circuits. https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&dl=0 circuit_notes.pdf] | problem list 4 |
| ??.10 | Circuit complexity. Classes AC^i and NC^i. Some functions have exponential circuit complexity. NC1 = Boolean formulas of polynomial size. Addition in AC0. Multiplication is in NC1. P is in P/poly. 3SAT is NP-complete. circuit_notes.pdf | problem list 5 |
| ??.10 | Directed Reachability is in SPACE(log^2 n). TQBF problem, its PSPACE-completeness. PSPACE = NPSPACE. NSPACE(s(n)) is in SPACE(s(n)^2) for space constructible s. | problem list 6 |
| ??.11 | Oracle computation definitions. There exists an oracle A for which PA = NPA. There is an oracle B such that PB is not equal to NPB. | problem list 7 |
| ??.11 | Probabilistic computation. Probabilistic machines, the class BPP, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. BPP is in P/poly. Most of it is also here and scribe1 scribe2 | problem list 8 |
| ??.11 | Approximation algorithms. Definition c-approximation algorithm. 2-approximation for vertex cover and greedy vertex cover is not optimal. (ln n + 1)-approximation for set cover. PTAS for the makespan problem. Based on MIT lecture. | |
| ??.11 | Parameterized complexity: The classes FPT and XP. Kernelization. Examples for vertex cover. Notes. | problem list 10 |
| ??.12 | Parameterized complexity: W-hierarchy, hardness from the exponential time hypothesis. presentation Notes | problem list 11 Update 05.12 |
| 11.12 | Colloquium. Rules and questions. Version Dec 8th. Shedule. | Sample exam |
| 18.12 | Colloquium. |
Artem Perfanov's lecture summaries source (Disclaimer: I did not check them):
| Date | Software engineering: parameterized complexity, FPT algorithms | Problem list |
|---|---|---|
| 05.03 | Recap from last lecture. More examples of kernels: linear programming kernel for vertex cover problem. programming task. presentation. | problem list 12
Update 03.12 |
| 12.03 | Linear programming kernel for VC, color coding, dynamic programming. Colorcoding from slide 39 | problem list 13 |
| 19.03 | Optional: problems that are FPT on graphs with small treewidth.(No recording, sorry.) | problem list 14 |
Exam
5 or 6 questions with the same difficulty as the homework questions. You have 3 hours time.
Each year, 1 of the questions is to prove that some problem is NP-complete. Do not forget to say why the problem is in NP.
Copies of Sipser's book, Arora&Barak, Mertens&Moore, will be available. (I you have these books or printed parts of them, please bring it.) Also, personal handwritten notes are allowed, but nothing else. Sample exam.
Additional reading
Recall that the most important book for our course is Sipser, Introduction to the theory of computation 3rd edition, 2013, chapters 3, 4, 7–9. This book is intended for Bachelor students.
The following book is popular with students theoretical computer science, because it contains most materials of our course in a concise way. Moreover, it presents many important advanced topics. I find the style of some proofs rather technical, but I like the topics in this book.
S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009
The course materials can also be found in various chapters of the following massive book (700 pages). It starts at beginning bachelor level and ends at an advanced master level. It is written in a pleasant style with excellent examples.
C. Moore and S. Mertens, The nature of computation, 2011.
This book gives an introduction to important recent research directions in computational hardness. It also studies specific topics (games and planar problems) in huge detail.
E. Demaine, W Gasarch, Haijaghayi, Computational intractability: a guide to lower bounds, 2023 current draft
This is an advanced textbook with background on parameterized algorithms.
M. Cygan, F. Fomin and 6 others, Parameterized algorithms, 2016
Grading
For AMI students:
Final score = 0.35 * [score homework] + 0.35 * [score colloquium] + 0.3 * [score exam]
Some homework assignments contain extra problems. Each solution of an extra problem will give 0.5 extra points on the final exam (which is graded out of 10). There will be around 10 extra problems. Rounding is applied only when the final score is transferred to the official grade. Arithmetic rounding is used. Autogrades. If only 6/10 for the exam is needed to get a final score of 10/10, then this will be given automatically.
Office hours
Bruno Bauwens: TBA
Subin Pulari: TBA
