Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-1-17 [2019/09/12 15:18]
phs [Plan et intervenants du cours 2019-2020]
cours:c-1-17 [2019/10/23 10:47] (current)
phs [Plan et intervenants du cours 2019-2020]
Line 10: Line 10:
  
  
-Les cours ont lieu le Mercredi de 8h30 à 10h30, suivis des TDs de 10h45 à 12h45, en salle Cournot 505, à l'ENS Paris-Saclay.  Voir le [[http://www.lsv.ens-cachan.fr/info-acces|plan]].+Les cours ont lieu le Mercredi de 8h30 à 10h30, suivis des TDs de 10h45 à 12h45, en salle Cournot 321, à l'ENS Paris-Saclay.  Voir le [[http://www.lsv.ens-cachan.fr/info-acces|plan]].
  
-Planning: **début du cours le 25 sept 2019**. Pas de cours ni TDs le 30 oct. Début de la 2ème partie du cours: 6 nov. +Planning: début du cours le 25 sept 2019. Pas de cours ni TDs le 30 oct. Début de la 2ème partie du cours: 6 nov.  
 + 
 +**Partial exam : Oct 23rd from 10h30 to 12h30**. This will be a written exam, consisting of exercises similar to what has been done in TD class, and will count for half of the global mark. The exam assumes knowledge of chapters 1, 2 and 3 of the lecture notes (and not chapter 4 that was not covered in class). Documents, including your lecture notes, are not allowed. On that day, the partial exam replaces the usual class followed by TD. 
 + 
 +Here is this year's [[http://www.lsv.ens-cachan.fr/~phs/partiel_complexite_avance_oct2019.pdf|partiel exam + correction]].
  
-Partial exam : Oct 23rd from 10h45 to 12h45.  
 Final exam : TBA Final exam : TBA
  
Line 36: Line 39:
 [[http://www.lsv.ens-cachan.fr/~goubault/Complexite/pcp.pdf|polycopié (2nd part)]].  (Note: il semble que le premier poly ait des problèmes de polices sous Acrobat Reader 9; aucun problème connu sous xpdf ou evince.) [[http://www.lsv.ens-cachan.fr/~goubault/Complexite/pcp.pdf|polycopié (2nd part)]].  (Note: il semble que le premier poly ait des problèmes de polices sous Acrobat Reader 9; aucun problème connu sous xpdf ou evince.)
  
-This page will be updated after each class with a summary of what has been covered.+This page will be updated after each class with a summary of what has been covered. Numbers, e.g. "(2.1)", refer to statement in the lecture notes.
  
 /* Exercices sheets and solutions are available on  [[http://www.lsv.ens-cachan.fr/~jacomme|Charlie's webpage]]. */ /* Exercices sheets and solutions are available on  [[http://www.lsv.ens-cachan.fr/~jacomme|Charlie's webpage]]. */
  
-/* +===== Sep. 252019 =====
-===== Sep. 192018 =====+
  
-  * Def (2.1) TIME(f(n)), SPACE(f(n)), NTIME, NSPACE, ..    +  * Def (2.1) TIME(n), SPACE(n), NTIME, NSPACE, ..    
-  * Speedup Theorem (2.2) +  * Speedup & Compression Theorems (2.2), including ∀ε>0 : TIME(f) ⊆ TIME(εf+n+2) 
-  * (2.3) REACH aka GAP is in NL aka NSPACE(log(n))+  * Lem (2.3) GAP aka REACH is in NL aka NSPACE(log(n)) 
 +  * Prop (2.6) GAP is in SPACE(log²(n))
    
-===== Sep. 26, 2018 ===== 
  
 +===== Oct. 2, 2019 =====
 +
 +  * A TM in space f(n) running on input x has at most ≈ |Q| × f(n)^{log |Σ|} × [log f(n)]^k x n configurations, i.e. O(n x f(n)^{1+log |Σ|}).
   * (2.4) NL ⊆ P   * (2.4) NL ⊆ P
-  * (2.6REACH is in SPACE(log²(n)) +  * (2.9Thm (Savitch 1970) NSPACE(f(n)) ⊆ SPACE(f²(n)) when f is constructible, increasing & ≥log. 
-  * (2.9Thm Savitch 1970 +  * (2.10) Hence NPSPACE=PSPACE 
-  * (2.10) NPSPACE=PSPACE +  * (2.16Thm (Immerman-Szelepcsényi 1987) coGAP is in NL 
-  * (2.12Deflogspace reductions & transitivity based on (2.11)+  * (2.17Hence NL=L.
  
-===== Oct. 32018 =====+===== Oct. 92019 =====
  
-  * (2.12) Def. logspace reductions & basic properties. REACH aka GAP is NL-complete for logspace reductions, SAT is NP-complete for logspace reductions. +  * (2.12) Def. logspace reductions, complete problems & basic properties.  
-  * GAP is in coNL +  * REACH aka GAP is NL-complete
-  * (2.17) coNL = NL +  * SAT is NP-complete.
-  * (2.18) Thm (Immerman-Szelepcsényi 1987) NSPACE(f(n)) = coNSPACE(f(n)) for f≥log+
  
-===== Oct. 102018 =====+===== Oct. 162019 =====
  
-  * (2.21) Thm (Stockmeyer-Meyer 1973) QBF is PSPACE-complete +  * Alternating Turing machines. 
-  * CIRCUIT_VALUE is PTIME-complete+  * (2.21) Thm (Stockmeyer-Meyer 1973) QBF is PSPACE-complete, hence PSPACE=APTIME. 
 +  * (3.8) Padding lemma, allowing (3.9) SPACE(poly(f(n)) = TIME(poly(f(n)) for any f constructible and s.t. f(n) ≥ n for large enough n. 
 +  * (3.18) CIRCUIT_VALUE is PTIME-complete, allowing PTIME=ALOGSPACE, and more generally (3.19) TIME(2^O(f(n)) = ASPACE(f(n)) with f as above.
  
 +/*
 ===== Oct. 17, 2017 ===== ===== Oct. 17, 2017 =====
  
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA