Groupe de Travail IGD-LIP "Complexité Algébrique"

Archives 1997-1998

Mercredi 17 septembre :
Herve Fournier (ENS Lyon)
Titre: "arbres de decision pour le probleme du sac-a-dos, et autres arrangements d'hyperplans".

Resume: On verra que des problemes "durs" (NP-complets, ou pire) peuvent etre resolus en temps polynomial dans le modele des arbres de decision (sur les reels). On abordera des developpements qui touchent a la fois a la geometrie algorithmique et a la complexite "abstraite" (structurelle).

Mercredi 24 septembre:
Pascal Koiran (LIP)
Titre: "Est-ce que les bornes inferieures sont plus faciles sur les reels ?"

Resume: Un des principaux buts de la complexite est de prouver des bornes inferieures superpolynomiales pour des problemes "naturels" (par exemple pour des problemes dans NP). Comme chacun le sait, cet objectif n'a pas ete atteint. Ceci motive en grande partie l'etude des modeles de calcul algebriques: on espere qu'il sera plus facile d'y prouver des bornes inferieures. Mais cet espoir est-il vraiment justifie ?? (amenez vos mouchoirs.)

Mercredi 1er octobre:
Pascal Koiran (LIP).
Titre: "arbres de decision pour les ensembles semi-algebriques"

Resume: Quelques remarques, conjectures et problemes a ce sujet.

Jeudi 9 octobre:
Olivier Chapuis (IGD)
Titre : "Separation dans le cas non uniforme"

Resume: On va montrer que si M est une structure arbitraire et si C est une classe de complexite (non uniforme) raisonnable alors il existe des problemes algorithmiques non uniformes qui ne sont pas dans C. La situation est la suivante (les hypotheses sur M concernent le nombre de types sans quanteurs sur vide) : Si M est de "nature denombrable", alors on trouve des problemes booleens qui ne sont pas P/polybool. Si M n'est pas de "nature finie", alors pour toute classe de complexite C (non uniforme) "bornee" il existe des problemes algorithmiques non uniformes qui ne sont pas dans C.

Jeudi 16 octobre :
Olivier Bournez (LIP),
"A propos de la decidabilite/indecidabilite du probleme de la stabilite pour les reseaux neuronaux / Probleme de la halte generalisee pour les machines de Turing"

Jeudi 30 octobre :
Christine Charretton (IGD),
"La classe #P des fonctions de comptage"

Resume: D'une fonction f definie sur les mots d'un alphabet fini et a valeurs dans N, on dit qu'elle appartient a la classe #P s'il existe une machine de Turing M, non deterministe travaillant en temps polynomial, telle que sur toute entree x, f(x) est exactement le nombre de calculs acceptant de M sur x. Il y a des problemes de comptage complets pour la classe #P (pour des reductions polynomiales parcimonieuses) , et etrangement il y en a dont le probleme de decision associe n'est pas NP, mais seulement P. Ensuite on s'interesse a la description logique de #P: ca marche et ca permet de prouver que #P est formee d'exactement 5 niveaux distincts.

Jeudi 27 novembre :
Nikolai Vereshchagin (LIP & Universite de Moscou)
"Threshold circuits of bounded depth"

Abstract: No nontrivial lower bounds are known for the class TC0 (Threshold circuits of bounded depth). I will present some lower bounds for TC0-circuits with some restrictions.
Jeudi 11 Decembre :
Pascal Koiran (LIP)
"Le probleme de la dimension est NP-complet sur R"

Resume: On verra que le calcul de la dimension des ensembles semi-algebriques est un probleme NP-complet sur R.
Jeudi 22 janvier :
Martin Matamala (Universite du Chili)
"Combien de composantes connexes y a t-il dans un ensemble difficile ?"

Resume: En definissant les ensembles creux ("sparse") comme etant ceux qui ont "peu" de composantes connexes et dont l'appartenance de deux point a la meme composante est decidable en temps polynomial, on a reussi a prouver une version du theoreme de Mahaney pour machines lineaires avec inegalites.
Jeudi 12 Fevrier :
Pascal Koiran (LIP)
"Elimination des parametres dans la hierarchie polynomiale"

Resume: Blum, Cucker, Shub et Smale ont montre que le probleme "P = NP ?" a la meme reponse dans tout corps algebriquement clos K de caracteristique 0. Ce resultat est base sur un theoreme d'elimination des parametres dans les machines sur K. On verra que tout ceci se generalise a la hierarchie polynomiale sur K.
Jeudi 26 Fevrier :
Olivier Chapuis (IGD)
"familles definissables d'ensembles definissables"

Resume: Soit M une structure dans un langage L. On se posera des questions du type suivant :
* Existe-t-il un enonce F(P) de L avec un nouveau predicat unaire P tel que si X est une partie finie de M, (M,X) satisfait F(P) ou P est interprete par X ssi X est de cardinal pair ?
* Supposons que M=(R,+,-,x,0,1,<). Existe-t-il un enonce F(P) de {+,-,x,0,1,<,P} ou P est un predicat binaire tel que si X est une partie definissable de MxM, (M,X) satisfait F(P) ssi X est connexe ?
Jeudi 12 Mars :
Nikolai Vereshchagin (LIP et universite de Moscou)
"Lower bounds for perceptrons recognizing connectivity"

Resume: Minsky and Papert have proved that perceptrons of small order cannot recognize whether the given two-dimensional image is connected or not. We prove that perceptrons of small order and small total weight cannot do this even if they are promised that the number of connected components in the image is large (as large as the square root of the number of pixels) if the image is not connected.
Jeudi 23 Avril :
Alexis Bes (Clermont)
"Les machines de Matiyasevich"

Resume: Je parlerai de machines theoriques introduites par Matiyasevich dans l'etude de problemes relatifs aux monoides partiellement commutatifs. Soient a,b deux entiers >0 et premiers entre eux, et soit q=a/b. Une q-machine consiste en un registre R, et un programme disposant des instructions suivantes: augmenter/diminuer R de 1, multiplier/diviser R par q (en prenant la partie entiere), tester si R=0?, tester si a|R, tester si b|R. Le probleme de la halte pour ces machines est ouvert. Je presenterai des resultats partiels, ainsi qu'un bon nombre de questions.
Jeudi 30 Avril :
Vincent Blondel (LIP et universite de Liege)
"Decidabilite et complexite de problemes en theorie des systemes et en theorie du controle"

Jeudi 14 Mai :
Herve Fournier (LIP)
"Un theoreme de transfert pour le probleme P=NP sur les reels avec addition et ordre"

Retour