Theory of Computing 2018 2019 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(Новая страница: «== General Information == [http://www.mi.ras.ru/~podolskii/files/computability1819/grading.pdf Grading] == Dates and Deadlines == == Course Materials == {|…») |
Bbauwens (обсуждение | вклад) |
||
Строка 12: | Строка 12: | ||
|- | |- | ||
! Summary !! Problem list | ! Summary !! Problem list | ||
+ | |- | ||
+ | || Time and space hierarchy theorems (see also Sipser Section 9.1) || [ ] | ||
+ | <!-- | ||
+ | |- | ||
+ | || Complexity class NP. Examples. Inclusions between P, NP and EXP. Non-deterministic TMs. Another definition of NP. Complexity class NEXP. Polynomial reductions, their properties. NP-hardness and NP-completeness, their properties. NP-completeness: CIRC-SAT, 3-SAT. || [http://www.mi.ras.ru/~podolskii/files/computability/prob_2.pdf Problem list 2] | ||
+ | |- | ||
+ | || NP-completeness: NAE-3-SAT, Exactly-1-3-SAT, IND-SET, Subset-SUM, 3-COLORING. || [http://www.mi.ras.ru/~podolskii/files/computability/prob_3.pdf Problem list 3] | ||
+ | |- | ||
+ | || Space complexity. Classes PSPACE and NPSPACE. Configuration graph. Inclusions between time and space classes. TQBF problem, its PSPACE-completeness. PSPACE = NPSPACE. NSPACE(s(n)) is in SPACE(s(n)^2) (additional material). Interpretation of PSPACE in terms of games. || [http://www.mi.ras.ru/~podolskii/files/computability/prob_4.pdf Problem list 4] | ||
+ | |- | ||
+ | || Probabilistic computation. Probabilistic machines, the class BPP, prime testing and Carmichael numbers, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. BPP is in P/poly. | ||
+ | || [http://www.mi.ras.ru/~podolskii/files/computability/prob_5.pdf Problem list 5] | ||
+ | |- | ||
+ | || Definition of Sigma_2 and Pi_2. BPP is in Sigma_2 and Pi_2. Computations with oracles, its simple properties. There are oracles A and B such that P^A is equal to NP^A and P^B is not equal to NP^B. | ||
+ | || [http://www.mi.ras.ru/~podolskii/files/computability/prob_6.pdf Problem list 6] <span style="color:red">Updated: 07.10.17</span> | ||
+ | |- | ||
+ | || Communication protocols. Functions EQ, GT, DISJ, IP. Fooling sets. Combinatorial rectangles. Rectangle size lower bound. Rank lower bound. Non-deterministic complexity. Communication complexity classes P, NP, coNP, intersection of NP and coNP. | ||
+ | || [http://www.mi.ras.ru/~podolskii/files/computability/prob_7.pdf Problem list 7] | ||
+ | |- | ||
+ | || D(f)=O(N^0(f)N^1(f)). Randomized communication complexity, definitions. R(EQ)=O(1). N^1(f) vs. R^1(f). Newman's theorem, formulation. | ||
+ | || [http://www.mi.ras.ru/~podolskii/files/computability/prob_8.pdf Problem list 8] | ||
+ | |- | ||
+ | || Proof of Newman's theorem, distributional complexity and the characterization of public coin communication complexity, the discrepancy method. | ||
+ | || [http://www.mi.ras.ru/~podolskii/files/computability/prob_9.pdf Problem list 9] | ||
+ | |- | ||
+ | || Randomized communication complexity of IP. Streaming algorithms. Finding the majority element. Deciding whether there is a most frequent element is hard. One-sided probabilistic complexity of disjointness. | ||
+ | || [http://www.mi.ras.ru/~podolskii/files/computability/prob_10.pdf Problem list 10] <span style="color:red">Updated: 22.11.17</span> | ||
+ | |- | ||
+ | || Property testing: definitions, testing of halfplanes, sorted listed, connectedness of graphs, testing of linearity. [https://www.dropbox.com/s/r35jr22fb3lfo3k/propTest.pdf?dl=0 Lecture notes.] Version 25.11.17 | ||
+ | || [https://www.dropbox.com/s/uzh9dur6aiy88dl/prob_11.pdf?dl=0 Problem list 11] <span style="color:red">Updated: 22.11.17</span> | ||
+ | |- | ||
+ | || Property testing: connectedness of graphs (cont.) and testing of monotonicity. (See notes from the previous lecture.) | ||
+ | || [https://www.dropbox.com/s/y2xujzeftsg6zlr/prob_12.pdf?dl=0 Problem list 12] | ||
+ | |- | ||
+ | || Property testing: lower bounds for monotonicity (see Sect 4 [http://theory.stanford.edu/~tim/w15/l/l8.pdf here]) and k-linearity using communication complexity. Approximation algorithms for some NP-complete problems (see seminar). | ||
+ | || [https://www.dropbox.com/s/5xsxqv098y5wmx0/prob_13.pdf?dl=0 Problem list 13] | ||
+ | |- | ||
+ | || The class PCP: definition, basic properties, and relation to with the MAX-Clique approximation problem. Beginning of the proof that NP is a subset of PCP(poly(n), 1). See Dexter Kozen, "Introduction to the theory of computation", lectures 18-20 (or see the book of Arora and Barak, chapter 11). | ||
+ | || [https://www.dropbox.com/s/gbg30ajwes45ne8/prob_14.pdf?dl=0 Problem list 14] | ||
+ | |- | ||
+ | || NP is a subset of PCP(poly(n),1) [continued]. Solutions of some extra problems. | ||
+ | || No problem list. | ||
+ | --> | ||
|} | |} | ||
+ | |||
+ | In the first lectures, we follow Sipser's book [https://theswissbay.ch/pdf/Book/Introduction%20to%20the%20theory%20of%20computation_third%20edition%20-%20Michael%20Sipser.pdf Introduction to the theory of computation]. |
Версия 17:28, 4 сентября 2018
General Information
Dates and Deadlines
Course Materials
Summary | Problem list |
---|---|
Time and space hierarchy theorems (see also Sipser Section 9.1) | [ ] |
In the first lectures, we follow Sipser's book Introduction to the theory of computation.