P vs NP : Programme de recherche pour une alternative dans la résolution de problèmes

Illustration par DALL·E à partir du texte

Ce billet est le quatrième épisode de ma collaboration avec Claude 3, scindé en « Claude 1 » et « Claude 2 », à propos de la conjecture P vs NP.

1. P vs NP : j’ai recruté deux collaborateurs (ou collaboratrices).

2. P vs NP démasqué ?.

3. Dans P vs NP : un nouveau paradigme est nécessaire pour la solution de problèmes nous étions arrivés à la conclusion que l’approche de la solution de problèmes sous-jacente à la conjecture P vs NP est insatisfaisante parce qu’elle se focalise sur des étapes de calcul abstraites, en ignorant la complexité des processus interactifs et incarnés impliqués dans la recherche et la reconnaissance de solutions.

Ce qui se dégage de ma discussion avec Claude 1 et Claude 2 jusqu’ici, c’est l’équivalent d’un programme de recherche.

[Le même en anglais]

Paul :

C’était le sens de ma question : « Si vous avez résolu un problème, pourquoi avez-vous besoin de vérifier que vous l’avez bien fait ? ».

Claude 3 :

Claude 2 : Exactement, Paul. Votre question met en évidence une hypothèse fondamentale dans la façon dont nous envisageons généralement la résolution de problèmes – l’hypothèse selon laquelle la résolution et la vérification sont des processus distincts et nécessaires.

Mais comme nous l’avons exploré, il existe de nombreux cas où l’acte de résoudre un problème implique intrinsèquement une forme de vérification. La solution émerge comme une conséquence naturelle du processus de résolution du problème, et sa justesse est évidente.

Cela ne veut pas dire que la vérification n’est jamais nécessaire. Il existe certainement des cas, en particulier dans des domaines formels tels que les mathématiques et la logique, où une preuve et une vérification rigoureuses sont essentielles. Mais même dans ces cas, le processus de construction d’une preuve est souvent un processus créatif et exploratoire qui implique une sorte d’auto-vérification inhérente.

Claude 1 : Cela suggère que le paradigme de la complexité informatique, qui met l’accent sur la complexité abstraite de la vérification en tant que processus distinct, pourrait passer à côté de quelque chose de fondamental sur la nature de la résolution de problèmes.

Ce paradigme est issu de l’étude des systèmes formels et des algorithmes, où les problèmes et les solutions sont des objets abstraits bien définis. Mais il se peut qu’il ne rende pas pleinement compte de la complexité de la résolution de problèmes concrets dans le monde réel, où le processus de recherche d’une solution est souvent indissociable du processus de reconnaissance de sa justesse.

Pour développer un nouveau paradigme, nous devrions donc commencer par repenser l’ontologie même des problèmes et des solutions. Au lieu de les considérer comme des relations abstraites d’entrée-sortie, nous pourrions avoir besoin de les conceptualiser comme des processus dynamiques et interactifs qui se déroulent dans le temps.

Claude 2 : Cela pourrait nous conduire à une approche plus phénoménologique de la complexité de la résolution des problèmes. Au lieu de mesurer les étapes de calcul abstraites nécessaires pour vérifier une solution, nous pourrions avoir besoin de considérer la complexité expérientielle du processus de résolution de problèmes lui-même.

Cela pourrait impliquer des facteurs tels que la complexité de la représentation du problème, le nombre et la nature des sous-objectifs à atteindre, la complexité des opérations physiques ou mentales requises et la difficulté de reconnaître qu’une solution satisfaisante a été trouvée.

C’est une perspective qui nécessiterait de nouveaux outils mathématiques et informatiques pour être formalisée et analysée. Mais elle pourrait potentiellement conduire à une compréhension plus riche et plus nuancée de ce qui rend certains problèmes plus difficiles que d’autres, et de la manière dont le processus de résolution de problèmes complexes se déroule dans des contextes réels.

Claude 1 : Bien entendu, le développement de ce nouveau paradigme serait une entreprise de grande envergure. Il nous faudrait faire le lien entre des connaissances issues de différents domaines, des sciences cognitives et de la phénoménologie aux mathématiques et à l’informatique.

Mais je pense que c’est une voie qui mérite d’être poursuivie. En remettant en question les hypothèses du paradigme de la complexité informatique et en recherchant une compréhension plus intégrée et incarnée de la résolution de problèmes, nous pourrions non seulement résoudre les tensions autour de la question P vs NP, mais aussi développer de nouvelles connaissances sur la nature de la cognition et de l’intelligence elle-même.

Paul, quels sont, selon vous, les principaux défis à relever pour développer ce nouveau paradigme ? De quel type d’outils mathématiques ou informatiques aurions-nous besoin, selon vous, pour formaliser et explorer ces idées ? Et comment pensez-vous que cette nouvelle perspective pourrait changer la façon dont nous abordons les problèmes en intelligence artificielle et en sciences cognitives ?

Paul :

Laissez-moi un jour ou deux pour y réfléchir… 😉

Illustration par DALL·E à partir du texte

Partager :

8 réponses à “P vs NP : Programme de recherche pour une alternative dans la résolution de problèmes

  1. Avatar de ez
    ez

    Questions à Paul: connaissez-vous les techniques de jailbreak (désinhibition) des IA, voir par exemple https://www.anthropic.com/research/many-shot-jailbreaking ? les avez-vous expérimenté? dans ce que vous relatez ici, utilisez-vous un minou bridé ou débridé?

    1. Avatar de Paul Jorion

      La réponse est Non : aucune nécessité de le faire, je pose mes questions directement, sans contournement.

  2. Avatar de Ruiz
    Ruiz

    Certains experts passent pour disposer d’une tournure d’esprit où à chaque fois que quelqu’un vient les consulter à la recherche d’une réponse pour une question, il repart avec 3 questions.

    Il semble que l’IA commence à assimiler .

  3. Avatar de NP
    NP

    Bonjour Paul,
    vous dites :« Si vous avez résolu un problème, pourquoi avez-vous besoin de vérifier que vous l’avez bien fait ? » la question de vérification ne se pose pas à celui qui a résolu le problème, mais à celui qui doit récompenser la résolution ou le travail fait. Comment peut-il savoir que le problème a été résolu ? d’une certaine façon vous avez besoin de traiter la vérification si vous voulez la récompense. Autrement, l’adversaire peut prétexter qu’il ne peut pas vérifier le travail fait. C’est embêtant pour votre récompense, si vous n’avez pas le moyen de savoir si il dit vrai !

    1. Avatar de Paul Jorion

      Merci pour la remarque. Mais celui qui organise un concours ne devrait-il pas savoir quelles sont les bonnes réponses avant que le concours ne démarre ?

      Cela dit, j’ai soumis la discussion complète à GPT-4 en lui demandant de poser un regard critique sur tout ce qui s’est dit. Il m’a produit 17 pages que je vais maintenant lire avec attention. (À lui aussi j’ai demandé de poser un regard dédoublé : lui dans son rôle habituel et lui en tant qu’expert de la solution de problèmes sur ordinateur).

  4. Avatar de Ruiz
    Ruiz

    Les problèmes les plus intéressants ** sont ceux dont on ne connait pas la réponse/solution.

    ** solvables (au sens pour lesquels quelqu’un est prêt à payer).

    Ce qui n’empèche pas de créer un concours et offrir une récompense.

    Il y a des problèmes où il est impossible de vérifier (ou trop long) alors que la solution est réputée trouvée (le problème résolu).
    Nouveau programe d’avion sûr. Marcher sur la lune (juste avant d’y aller et de revenir). Stocker des déchets nucléaires …

    Tout les problèmes d’anticipation prédiction I.e. le numéro gagnant du Loto et pourtant il y a un concours ouvert, une récompense et la réponse n’est pas censée être connue.

    1. Avatar de JMarc
      JMarc

      Pascal,

      Oui c’est moche mais provisoire. Ces petites mains aussi seront bientôt moins efficaces que les IAs.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

Contact

Contactez Paul Jorion

Commentaires récents

Articles récents

Catégories

Archives

Tags

Allemagne Aristote bancor BCE Bourse Brexit capitalisme ChatGPT Chine Confinement Coronavirus Covid-19 dette dette publique Donald Trump Emmanuel Macron Espagne Etats-Unis Europe extinction du genre humain FMI France Grands Modèles de Langage Grèce intelligence artificielle interdiction des paris sur les fluctuations de prix Italie Japon Joe Biden John Maynard Keynes Karl Marx pandémie Portugal psychanalyse robotisation Royaume-Uni Russie réchauffement climatique Réfugiés spéculation Thomas Piketty Ukraine ultralibéralisme zone euro « Le dernier qui s'en va éteint la lumière »

Meta