Séminaire (organisé par l’équipe de recherche RO)

Yu LI

Maître de Conférence à l’Université Picardie Jules Verne


La perte de non déterminisme de la théorie de la complexité des algorithmes


Lundi 2 février 2015 à 10 h en salle K110 (PG)

Résumé :

Dans cet exposé, nous discutons la perte de la notion "nondéterminisme" de la définition actuelle de NP en remettant en cause l’équivalence de deux définitions de NP. La première définition de NP est basée sur la solvabilité : NP est une classe des problèmes qui peuvent être résolus en temps polynomial sur une machine de Turing nondéterministe, et la deuxième définition est basée sur la verfiabilité : NP est une classe des problèmes qui peuvent être vérifiés en temps polynomial sur une machine de Turing déterministe. L’académie actuelle considère que ces deux définitions sont équivalentes. Par conséquence, la définition basée sur la vérifiabilité est utilisée comme la définition standard de NP, qui cause la perte de nondéterminisme de NP, et provoque la grande difficulté pour comprendre la relation P versus NP. Nous questionnons cette équivalence de deux points de vue : la reconnaissance de problèmes, et la représentation de problèmes. Nous interprétons certaines opinions courantes qui acceptons cette équivalence, et la preuve du théorème de Cook qui a engendré cette équivalence. Nous relevons des erreurs cognitives : la confusion de nondéterminisme et déterminisme. Nous argumentons que la compréhension de P versus NP se situe d’abord au niveau de la cognition, et après au niveau de la logique mathématique.

Seminars


Mardi 24 octobre 2017

Séminaire à 14h00 en GI042 (Bâtiment Blaise Pascal - UTC) présenté par Richard NELSON, Maître de conférences à l’Université de Waikato à Hamilton (Nouvelle-Zélande).
WAND : Network Research at the University of Waikato.


Mardi 10 mai 2016

Séminaire à 14 h 30 en GI042 présenté par Christophe DENIS, Chargé de Formation et de Recherche au Centre de mathématiques et de leurs applications (CMLA), ENS Cachan. « Verificarlo : checking the floating point accuracy of scientific codes »


Lundi 14 mars 2016

Séminaire à 9 h en GI042, présenté par Ahcène Bounceur, Maître de conférence, HDR, à l’Université de Bretagne Occidentale (UBO). « CupCarbon : A New Platform for Simulating Smart Wireless Sensor Networks (SWSN) »


Mardi 9 février 2016

Séminaire à 14 h en GI042 présenté par Fabio D’Andreagiovanni, Chercheur senior et Directeur de projet au département d’optimisation de Zuse Institute Berlin (ZIB), Berlin (Allemagne). « Multiband Robust Optimization : theory and applications »


Pages 1 | 2 | 3 | 4 | 5 | 6 | 7




Actualités
Vidéothèque
Téléchargements
Annuaire



FR SHIC 3272

Collegium UTC/CNRS