Theory of Computing 2018 2019 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Новая страница: «== General Information == [http://www.mi.ras.ru/~podolskii/files/computability1819/grading.pdf Grading] == Dates and Deadlines == == Course Materials == {|…»)
 
Строка 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

Grading

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.