*************************************************************************

		Seminaire du LIP : AUTOUR DE "P = NP ?"
	
			Mercredi 18 fevrier 1998
		
	  Amphi B (4eme etage), ENS Lyon (46 allee d'Italie a Gerland)

*************************************************************************


Programme de la demi-journee
****************************

* 13h30 - 13h50 Pascal Koiran (LIP/ENS-Lyon): 
		Introduction.

* 13h50 - 14h35 Nikolai Verechtchaguine (LIP et Universite de Moscou) : 
                Interactive proofs (a new view on what is a proof).

* 15h   - 15h45 Sophie Laplante (Paris 11) : 
          Complexite de Kolmogorov pour les circuits.
          
* 15h45 - 16h30 Alessandra Carbone (Paris 12) : 
                 P, NP, CO-NP et les systemes de preuves formels.
                 
  -- Introduction.    
  ------------------           
  Pascal Koiran (LIP/ENS-Lyon): 
  
Concepts de base: 
P, NP, problemes NP-complets, circuits booleens...                 


  --Interactive proofs (a new view on what is a proof).
  -----------------------------------------------------
  Nikolai Verechtchaguine (LIP et Universite de Moscou) : 
                
Abstract: One of the main philosophical achievements of Complexity
Theory is a new concept of proof.

In the regular understanding, a proof is a text written by a
Prover.  The proof can be verified at any time by the
Verifier.  The verification procedure should be completely
deterministic and simple.

In the new understanding, a proof doesn't exist as a
material object.  The Prover convinces Verifier that a fact
is true by exchanging messages with him, and the interaction
is essentially two-way.  After having been convinced the
Verifier cannot transmit the proof to any third person.  The
verification procedure again should be simple, however not
necessarily deterministic.  The Verifier may use fair coin
tossing during the interaction with the Prover, and it is
allowed that, with small probability (say 10^{-10}), Prover
will convince Verifier that some false assertion is true.

A widely believed hypothesis is that interactive proof
systems are much more powerful that regular ones. 


  -- Complexite de Kolmogorov pour les circuits.
  ----------------------------------------------
  Sophie Laplante (Paris 11) : 

On mesure, en complexité de Kolmogorov, la longueur du plus court 
programme qui produit en sortie une chaîne donnée.  Cette mesure
très locale de complexité se prête tres bien aux preuves de bornes   
inferieures dans les modèles non-uniformes tels que les circuits.  
On présentera dans cet exposé un survol de la technique dite de 
l'incompressibilité, qu´on illustrera par une preuve du classique 
résultat de Yao et Håstad sur la taille des circuits requis pour 
calculer la fonction parité.


  -- P, NP, CO-NP et les systemes de preuves formels.
  ---------------------------------------------------
  Alessandra Carbone (Paris 12) : 

Un systeme de preuves propositionnelles peut etre envisage comme un
algorithme non-deterministe (CO-NP complet) du probleme
d'insatisfaisabilite. Cette idee a genere dans les dernieres annees
beaucoup d'activite de recherche sur les connections entre systemes de
preuves formels et theorie de la complexite. Entre les problemes
abordes on trouvera le calcul de bornes inferieures pour les
differents systemes de la hierarchie propositionnelle, les liens entre
la combinatoire de la structure des preuves et les bornes inferieures,
la recherche de symetries dans les preuves, juste pour nommer quelques uns.
On presentera un panorama de ce domaine en pleine croissance.