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.



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



FR SHIC 3272

Collegium UTC/CNRS