{"id":1897,"date":"2023-09-29T09:27:36","date_gmt":"2023-09-29T07:27:36","guid":{"rendered":"https:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=1897"},"modified":"2024-10-04T09:19:12","modified_gmt":"2024-10-04T07:19:12","slug":"zlozonosc-obliczeniowa-computational-complexity-2023-2024","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/2023-2024\/zlozonosc-obliczeniowa-computational-complexity-2023-2024","title":{"rendered":"Z\u0142o\u017cono\u015b\u0107 Obliczeniowa \/ Computational Complexity 2023\/2024"},"content":{"rendered":"<p>A course on computational complexity for 4th year students (1st year of MSc programme). Previous iterations of this course: <a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/2022-2023\/zlozonosc-obliczeniowa-computational-complexity\">2022\/2023<\/a> and <a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/2020-2021\/computational-complexity-zlozonosc-obliczeniowa\">2020\/2021<\/a><\/p>\n<p><!--more--><\/p>\n<h2>Rules<\/h2>\n<p>Your grade will consist of:<\/p>\n<ul>\n<li>10% quizzes. Lectures will have a quizzes on google classroom with several yes\/no questions to check if you are paying attention.<\/li>\n<li>40% homeworks. There will be 4 homeworks, some programming and some theory.<\/li>\n<li>50% oral exam. At the end, there will be an oral exam.<\/li>\n<\/ul>\n<p>Notice that there is no written exam, midterm or final. That is why the homeworks are bigger than usual. The exact point thresholds for the grades will appear later, but I promise that 50% (or less) will give you a passing grade (dostateczny).<\/p>\n<p>The examiner for your oral will be your tutorial instructor (\u0107wiczeniowiec) <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/quicklatex.com\/cache3\/9e\/ql_10e92c12fe4eb893100e9f96c7f5069e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#105;&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"10\" width=\"9\" style=\"vertical-align: -1px;\"\/> {Czerwi\u0144ski, Parys, Pilipczuk, Pilipczuk} You can negotiate the date of the oral exam with your, in justified cases it is possible to have the oral exam at an earlier date.<\/p>\n<div class=\"\"><b class=\"\">How much effort is expected?<\/b><\/div>\n<p>I expect that you, as a smart student, will:<\/p>\n<div class=\"\">\n<div class=\"\">1. Attend the lecture each week<\/div>\n<div class=\"\">2. Take 10-20 minutes to solve the quiz<\/div>\n<div class=\"\">3. Participate in the exercise session<\/div>\n<div class=\"\">4. Take, on average, 7 hours to solve each of the 4 homework assignments<\/div>\n<div class=\"\">5. Take around 15-20 hours to prepare for the oral exam (e.g. you rewatch every lecture and think about it a bit)<\/div>\n<div class=\"\">The difficulties of the quizzes, homeworks, and the oral exams will be designed with these criteria in mind. I will send surveys to check if these criteria are met. If you believe that your effort deviates significantly from these criteria, let me know.<\/div>\n<div class=\"\"><\/div>\n<div class=\"\"><b class=\"\">Quizzes<\/b>. I expect that you do the quiz on your own, without discussing the answers with colleagues. For this reason, you do not need to obsess over perfect answers \u2013 at the end of the semester you will still get a full score for the quiz if you had 80% answers right. The purpose of the quiz is to see if you understand the lecture well.<\/div>\n<div class=\"\"><\/div>\n<div class=\"\"><b class=\"\">Homework<\/b>. There will be around 4 homeworks, some programming, some not. It is ok if you discuss the homework with a small number of colleagues, but you should make a serious effort to solve it on your own, and you should definitely write your own answer alone.<\/div>\n<div class=\"\"><\/div>\n<div class=\"\"><b class=\"\">Oral<\/b> <b class=\"\">exam<\/b>. For each of the lectures, I will publish corresponding exam questions. The questions at the oral exam will be selected from these. Some questions will be marked as \u201c5\u201d questions, which will be needed only if you want to get the top grade \u201c5\u201d.<\/div>\n<\/div>\n<p>&nbsp;<\/p>\n<h2>Lectures<\/h2>\n<p>I will try to have updated slides together with sound recordings, with links below. These should be useful for revising and in case you miss a lecture. I do recommend that you also attend the actual live lectures. The live lectures will not be identical to the recorded slides, I might end up using the blackboard and not the slides altogether.<\/p>\n<p>The lectures use a slide system that I am developing, so please send me bug reports! These lectures are roughly once per week, but some lectures are longer so there is no exact correspondence. You can find old slides in the old lectures <a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/2022-2023\/zlozonosc-obliczeniowa-computational-complexity\">2022\/2023 (without sound)<\/a> and <a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/2020-2021\/computational-complexity-zlozonosc-obliczeniowa\">2020\/2021 (with sound).<\/a><\/p>\n<p><a href=\"https:\/\/mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2023\/Lecture_1._Turing_machines\/\"><strong>Turing machines (October 3)<\/strong><\/a><\/p>\n<ul>\n<li>Definition of Turing machines<\/li>\n<li>Decidability and semi-decidability<\/li>\n<li>Undecidability of the halting problem<\/li>\n<\/ul>\n<p>Questions for the oral exam:<\/p>\n<ul>\n<li>prove that the halting problem is undecidable<\/li>\n<\/ul>\n<p><a href=\"https:\/\/mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2023\/Lecture_2._Space_and_time\/\"><strong>Space and time (October 10)<\/strong><\/a><\/p>\n<ul>\n<li>The basic complexity classes: NL \u2286 P \u2286 NP \u2286 PSPACE \u2286 EXPTIME,<\/li>\n<li>separation of P and EXPTIME<\/li>\n<li>PSPACE = NPSPACE (Savitch)<\/li>\n<li>machines in finite space that always halt (Sipser Theorem)<\/li>\n<li>NL = coNL (Immerman and Szelepcsenyi Theorem)<\/li>\n<\/ul>\n<p>Questions for the oral exam:<\/p>\n<ul>\n<li>Prove that P &lt; EXPTIME<\/li>\n<li>Prove that PSPACE = NPSPACE<\/li>\n<li>Prove the Sipser Theorem<\/li>\n<li>Prove the Immerman and Szelepcsenyi Theorem<\/li>\n<\/ul>\n<p><a href=\"https:\/\/mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2023\/Lecture_3._Reductions\/?step=0\"><strong>Reductions and complete problems (October 11, 17)<\/strong><\/a><\/p>\n<ul>\n<li>Turing and Karp reductions<\/li>\n<li>an NP-complete problem<\/li>\n<\/ul>\n<p>Questions for the oral exam:<\/p>\n<ul>\n<li>Explain the difference between Turing and Karp reductions<\/li>\n<li>Prove that the NP halting problem is NP-complete<\/li>\n<\/ul>\n<p><a href=\"https:\/\/mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2023\/Lecture_3b._Complete_problems_for_important_classes\/?step=0\"><strong>\u00a0Complete problems for important classes (October 17, 23, 30)<\/strong><\/a><\/p>\n<ul>\n<li>Sat as an NP-complete problem<\/li>\n<li>QBF as a PSPACE-complete problem<\/li>\n<li>alternating reachability as P-complete problem<\/li>\n<li>the Baker-Gill-Solovay Theorem.<\/li>\n<\/ul>\n<p>Questions for the oral exam:<\/p>\n<ul>\n<li>Prove that Sat is NP-complete and that QBF is PSPACE-complete<\/li>\n<li>Prove that reachability is NL-complete, and alternating reachability is P-complete<\/li>\n<\/ul>\n<p><a href=\"https:\/\/mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2023\/Lecture_3c._Two_diagonalisation_theorems\/?step=0\"><strong>Two diagonalisation theorems about P = NP (October 30, November 7)<\/strong><\/a><\/p>\n<ul>\n<li>Ladner&#8217;s Theorem<\/li>\n<li>the Baker-Gill-Solovay Theorem.<\/li>\n<\/ul>\n<p>Questions for the oral exam:<\/p>\n<ul>\n<li>Prove Ladner&#8217;s Theorem<\/li>\n<li>Prove the Baker-Gill-Solovay Theorem<\/li>\n<\/ul>\n<p><a href=\"https:\/\/mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2023\/Lecture_4._Introduction_to_circuits\/?step=0\"><strong>Introduction to circuits (November 7)\u00a0<\/strong><\/a><\/p>\n<ul>\n<li>Circuits and their &#8220;parallel algorithm&#8221; intuition<\/li>\n<li>Circuit descriptions of P and P\/p0ly<\/li>\n<li>AC<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-5aef4352fcf073bb4e26d09e52b24d46_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#94;&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"5\" width=\"7\" style=\"vertical-align: 6px;\"\/> and NC<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-5aef4352fcf073bb4e26d09e52b24d46_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#94;&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"5\" width=\"7\" style=\"vertical-align: 6px;\"\/><\/li>\n<\/ul>\n<p>Questions for the oral exam:<\/p>\n<ul>\n<li>Define the class P\/Poly and show that it is equal to polynomial size circuits<\/li>\n<\/ul>\n<p><a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2023\/Lecture_5._Parity_not_in_AC0\/\"><strong>Parity not in AC0\u00a0<\/strong><\/a><\/p>\n<ul>\n<li>parity is not in AC<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-f709c1e24dd30fa8a21a096753b6c56d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#94;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"6\" style=\"vertical-align: 6px;\"\/><\/li>\n<\/ul>\n<p>Questions for the oral exam:<\/p>\n<ul>\n<li>(Only if you want grade 5) Prove that parity is not in AC<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-f709c1e24dd30fa8a21a096753b6c56d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#94;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"6\" style=\"vertical-align: 6px;\"\/><\/li>\n<\/ul>\n<p><a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2023\/Lecture_6._Randomised_algorithms\/\"><strong>Randomisation\u00a0<\/strong><\/a><\/p>\n<ul>\n<li>the class RP \u2286 BPP \u2286 PP<\/li>\n<li>examples of RP algorithms, including polynomial identity testing and perfect matchings<\/li>\n<li>PP contains NP<\/li>\n<\/ul>\n<p>Questions for the oral exam:<\/p>\n<ul>\n<li>Define the classes RP, BPP and PP<\/li>\n<li>Give RP algorithms for: evaluating straight line programs and polynomial identity testing<\/li>\n<\/ul>\n<p><a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2023\/Lecture_7._Randomised_algorithms_2\/\"><strong>Derandomisation<\/strong><\/a><\/p>\n<ul>\n<li>two techniques for derandomisation illustrated on max cut<\/li>\n<li>Adleman&#8217;s Theorem on BPP \u2286 P\/Poly<\/li>\n<\/ul>\n<p>Questions for the oral exam:<\/p>\n<ul>\n<li>Explain the two derandomised algorithms for max cut<\/li>\n<li>Prove Adleman&#8217;s Theorem<\/li>\n<\/ul>\n<p><a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2023\/Lecture_8._Fine_grained_complexity\/\"><strong>Fine-grained complexity<\/strong><\/a><\/p>\n<ul>\n<li>SETH \u27f9 Orthogonal vectors conjecture<\/li>\n<li>Orthogonal vectors conjecture \u00a0\u27f9 NFA evaluation needs quadratic algorithms<\/li>\n<\/ul>\n<p>Questions for the oral exam:<\/p>\n<ul>\n<li>Prove:\u00a0SETH \u27f9 Orthogonal vectors conjecture<\/li>\n<li>Prove: Orthogonal vectors conjecture \u00a0\u27f9 NFA evaluation needs quadratic algorithms<\/li>\n<\/ul>\n<p><a href=\"https:\/\/mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2023\/Lecture_9._Parameterized_complexity\/\"><strong>Parametrized complexity<\/strong><\/a><\/p>\n<ul>\n<li>An algorithm for vertex cover that is linear when the size of the vertex cover is fixed<\/li>\n<li>The class FPT and FPT-reductions<\/li>\n<li>An FPT algorithm for 3-colourability on bounded treewidth<\/li>\n<\/ul>\n<p>Questions for the oral exam:<\/p>\n<ul>\n<li>Define the class FPT and show that vertex cover is in it<\/li>\n<li>Show FPT reductions, both ways, between the k-clique problem and Turing machines with accepting computations of length k.<\/li>\n<\/ul>\n<p>The remaining lectures are not part of the oral exam.<\/p>\n<p><a href=\"https:\/\/mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2023\/Lecture_10._Streaming\/\"><strong>Streaming<\/strong><\/a><\/p>\n<ul>\n<li>An algorithm for \u03b5-heavy hitters<\/li>\n<li>An algorithm for unique names<\/li>\n<\/ul>\n<p><a href=\"https:\/\/mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2022\/Lecture_10._Quantum\/?step=0\"><strong>Lecture 10. Quantum computation<\/strong><\/a><\/p>\n<ul>\n<li>BPP via probabilistic circuits<\/li>\n<li>quantum circuits<\/li>\n<li>the class BQP (bounded error quantum polynomial time)<\/li>\n<\/ul>\n<p><a href=\"https:\/\/mimuw.edu.pl\/~bojan\/slides\/slajdomat\/teaching\/complexity\/complexity2022\/Lecture_11._Simon's_algorithm\/?step=0\"><strong>Lecture 11. Simon&#8217;s algorithm<\/strong><\/a><\/p>\n<ul>\n<li>Simon&#8217;s algorithm<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h2>Homework<\/h2>\n<p>There will be several homework assignments, including programming assignments.<\/p>\n<p>&nbsp;<\/p>\n<h4>Homework 1<\/h4>\n<p>Your goal will be to write a python program, \u00a0which transforms a two-tape machine into an equivalent one-tape machine. The details are on the classroom page. You play with Turing machines using something called &#8220;jupyter notebook&#8221;. Once you have <a href=\"https:\/\/jupyter.org\/install\">installed jupyter<\/a>, download the file <a href=\"https:\/\/github.com\/bojanczyk\/turingJupyter\">turingPython.ipynb, <\/a>\u00a0and then type &#8220;jupyter lab turingPython.ipynb&#8221; into the command line from the directory containing the downloaded file.<\/p>\n<div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>A course on computational complexity for 4th year students (1st year of MSc programme). Previous iterations of this course: 2022\/2023 and 2020\/2021<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1894,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-1897","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1897"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=1897"}],"version-history":[{"count":17,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1897\/revisions"}],"predecessor-version":[{"id":1988,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1897\/revisions\/1988"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1894"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=1897"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}