Bonjour,
Je suis néophyte dans le domaine de l'informatique, je vais donc poser des questions assez basiques... Ou sortir des inanités !
En me renseignant sur la page wikipédia du théorème PCP (http://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_PCP), je n'ai pas compris la notion de langage :
"C'est le vérificateur qui décide si une entrée donnée appartient au langage. Si l'entrée est dans le langage, on demande que le vérificateur accepte toujours le mot, pourvu qu'on lui fournisse un oracle adéquat."
Le langage correspond-t-il à la démonstration qu'on veut vérifier par PCP ?
De plus, je me fais cet idée du théorème : il permet de vérifier une démonstration d'un calcul / théorème (souvent longue, d'où l'utilité) en prenant chaque étape du calcul / théorème, et en vérifiant une partie (l'oracle) de chacune de ces étapes (par vérification de certains bits si on est en système binaire) au lieu de vérifier l'intégralité du message des étapes (d'où le gain de temps), et ce grâce à un vérificateur.
Ai-je bien compris...?
Enfin, le théorème PCP pourrait servir à résoudre des problèmes de type NP sans résoudre mais en contournant le problème P = NP. Il permettrait de vérifier chaque calcul / résultat des différentes branches de calcul d'un problème NP beaucoup plus rapidement (c'est à dire en temps polynomial et non exponentiel).
Je n'utilise peut-être pas les bons termes, j'en suis désolé...
Merci d'avance !
-----