Quelle est la classe de complexité la plus étroitement associée à ce que l’esprit humain peut accomplir rapidement?

Cette question est quelque chose que je me pose depuis un moment.

Lorsque les gens décrivent le problème P vs NP, ils comparent souvent la classe NP à la créativité. Ils notent que la composition d'une symphonie de qualité Mozart (analogue à une tâche NP) semble beaucoup plus difficile que de vérifier qu'une symphonie déjà composée est de qualité Mozart (analogue à une tâche P).

Mais NP est-il vraiment la "classe de créativité"? N'y a-t-il pas beaucoup d'autres candidats? Il y a un vieil adage: "Un poème n'est jamais fini, il est seulement abandonné." Je ne suis pas un poète, mais cela me rappelle l'idée de quelque chose pour lequel il n'y a pas de réponse juste et définitive qui puisse être vérifiée rapidement ... cela me rappelle davantage le PNO et les problèmes tels que la TAUTOLOGIE que NP ou SAT. Je suppose que ce que je veux dire, c'est qu'il est facile de vérifier quand un poème est "faux" et doit être amélioré, mais difficile de vérifier quand un poème est "correct" ou "terminé".

En effet, NP me rappelle plus la logique et la pensée gauche que la créativité. Les preuves, les problèmes d'ingénierie, les énigmes de Sudoku et d'autres problèmes stéréotypés de «cerveau gauche» sont plus faciles à vérifier et faciles à vérifier du point de vue de la qualité que la poésie ou la musique.

Ma question est donc la suivante: quelle classe de complexité capture le plus précisément la totalité de ce que l’être humain peut accomplir avec son esprit? Je me suis toujours demandé sans rien faire (et sans aucune preuve scientifique à l'appui de mes hypothèses) si le cerveau gauche n'était peut-être pas un solveur SAT approximatif et si le cerveau droit n'était pas un résolveur TAUTOLOGY approximatif. Peut-être que l'esprit est configuré pour résoudre les problèmes de PH ... ou peut-être qu'il peut même résoudre les problèmes de PSPACE.

J'ai offert mes pensées ci-dessus; Je suis curieux de savoir si quelqu'un peut offrir de meilleures informations à ce sujet. Pour formuler ma question de manière succincte: je demande quelle classe de complexité doit être associée à ce que l’esprit humain peut accomplir et comme preuve ou argument à l’appui de votre point de vue. Ou bien, si ma question est mal posée et qu'il n'est pas logique de comparer les classes humaines et les classes de complexité, pourquoi est-ce le cas?

Merci.

Mise à jour : j'ai tout laissé sauf le titre intact ci-dessus, mais voici la question que je voulais vraiment poser: quelle classe de complexité est associée à ce que l'esprit humain peut accomplir rapidement ? Qu'est-ce que le "temps humain polynomial", si vous voulez? De toute évidence, un humain peut simuler une machine de Turing avec un temps et des ressources infinis.

Je soupçonne que la réponse est PH ou PSPACE, mais je ne peux pas vraiment énoncer un argument intelligent et cohérent pour expliquer pourquoi tel est le cas.

Notez également: je suis principalement intéressé par ce que les humains peuvent approcher ou "faire la plupart du temps". De toute évidence, aucun humain ne peut résoudre les cas difficiles de SAT. Si l'esprit est un approximateur X approximatif et que X est complet pour la classe C , c'est important.

Je ne prétends pas que cette réponse est complète, mais voici quelques réflexions qui, espérons-le, vont dans le sens de ce que vous recherchez.

$n \to \infty$

Les gens semblent généralement bien se débrouiller avec des cas finis de puzzles NP-complets, tout en les trouvant non-triviaux. Les instances finies de jeux PSPACE-complete que nous jouons sont considérées comme l'une des tâches intellectuelles les plus difficiles de ce type. Ceci suggère au moins que PSPACE "frappe la limite supérieure" de nos capacités. (Pourtant, nos adversaires dans ces jeux complets avec PSPACE sont généralement d’autres personnes. Même lorsque les adversaires sont des ordinateurs, les ordinateurs ne sont pas des adversaires parfaits. aussi la technicité que certaines généralisations de ces jeux sont EXP-complet au lieu de PSPACE-complet.)

Dans une certaine mesure, la taille des problèmes rencontrés dans les casse-tête / jeux réels a été calibrée en fonction de nos capacités. Sudoku 4x4 serait trop facile, donc ennuyeux. Un Sudoku 16x16 prendrait trop de temps (pas plus que la durée de vie de l'univers, mais plus que les gens sont généralement disposés à s'asseoir pour résoudre un puzzle de Sudoku). 9x9 semble être la taille "Goldilocks" pour les personnes qui résolvent le Sudoku. De même, jouer à Free Cell avec un jeu de 4 combinaisons de 13 cartes et 4 cellules libres semble être la solution idéale pour être résolu mais difficile pour la plupart des gens. (D'un autre côté, une des personnes les plus intelligentes que je connaisse est capable de résoudre les jeux Free Cell comme si elle comptait juste des nombres naturels "1,2,3,4, ...") De même pour la taille de Go and Chess planches.

Avez-vous déjà essayé de calculer un permanent 6x6 à la main?

$< 10^{10}$

À l'inverse, pour les problèmes rencontrés dans EXP, toute taille de problème inférieure au "talon de l'exponentielle" a une chance d'être résolue par la plupart des gens dans des délais raisonnables.

En ce qui concerne le reste de PH, il n'y a pas beaucoup (aucun?) De jeux naturels auxquels on joue avec un nombre de tours déterminé. Ceci est également lié au fait que nous ne connaissons pas beaucoup de problèmes naturels complets pour des niveaux de PH supérieurs au tiers.

Comme l'a mentionné Serge, FPT a un rôle à jouer ici, mais (je pense) principalement dans le fait que certains problèmes ont naturellement plus d'une "taille d'entrée" qui leur est associée.

La thèse de la cognition tractable postule que les capacités cognitives humaines sont limitées par la tractabilité informatique. De cette manière, la thèse de P-Cognition utilise le temps polynomial déterministe comme modèle de calculabilité du calcul, alors que dans l'article ci-dessous, il est avancé que la thèse de FPT-Cognition est plus appropriée. Voir l'article d'Iris van Rooij dans l'édition de juin 2009 du bulletin Parameterized Complexity Newsletter pour une discussion plus détaillée et des pointeurs vers d'autres documents.

• Iris van Rooij. La thèse de la cognition tractable . Cognitive Science, 32, pp. 939-984, 2008.
• Iris van Rooij. Paramètres qui rendent Cognitive Work Light. Nouvelles FPT: Bulletin sur la complexité paramétrée, juin 2009 .

Je pense qu’on essaie d’extrapoler à partir du genre de choses que le cerveau humain semble calculer, et j’estime qu’il serait préférable de prendre le point de vue opposé et d’extrapoler à partir du modèle informatique qu’il est.

$TC^0$

En outre, je ne suis pas d'accord avec l'affirmation de la question selon laquelle l'esprit humain peut simuler une machine de Turing. Au lieu de cela, il peut simuler le contrôle fini de la machine de Turing. Pour effectuer des tâches très complexes, il semble nécessaire de pouvoir enregistrer des informations sur une "bande".

Les classes de complexité sont définies en termes de complexité asymptotique. Par conséquent, elles ne correspondent pas bien aux capacités cognitives des humains, qui sont nécessairement limitées à des problèmes de taille limitée.

La règle générale est la suivante: si quelque chose est facile pour un ordinateur, cela peut être difficile pour un humain, et inversement, si c'est difficile pour un ordinateur, cela peut être facile pour un humain.

Ici, "facile / difficile pour un ordinateur" fait référence à la facilité de manipulation, pas à une classe de complexité abstraite.

Par exemple, ajouter une liste de 1 milliard d'entiers est facile pour un ordinateur moderne et difficile pour un humain, tandis que produire une description verbale d'une image est facile pour un humain mais difficile (actuellement impossible dans le cas général) pour un ordinateur.

La recherche en intelligence artificielle a montré que de nombreuses tâches cognitives que l'homme et les animaux accomplissent facilement, voire inconsciemment dans certains cas, peuvent être modélisées comme des problèmes difficiles à résoudre. Les humains ne sont pas en mesure de trouver des solutions optimales à ces problèmes pour toutes les tailles, mais ils sont capables de trouver des solutions heuristiques pour des tailles pratiques bien meilleures que les meilleurs algorithmes d'IA connus.

Notez également que la distinction cerveau gauche / cerveau droit que vous mentionnez est trop simpliste et obsolète. La latéralisation des fonctions cérébrales est beaucoup plus subtile et peut même varier d’un individu à l’autre.

Si nous choisissons d'étudier le cerveau humain lui-même plutôt que la façon dont les humains utilisent leur cerveau pour résoudre des problèmes, je ne pense pas qu'il s'agisse d'un problème de complexité, mais plutôt de calculabilité. Comme chaque MT a besoin d'une fonction de transition, un humain peut imiter ses étapes. Par conséquent, le cerveau humain est complet de Turing.

Dans le sens inverse, les MT peuvent-elles calculer tout ce que les humains font? La réponse courte est que nous ne savons pas. En supposant que la thèse de Church-Turing soit vraie, que la réponse change ou non dépend de votre vision du monde (philosophique, spirituel, religieux ou autre). Dans ce cas, on peut affirmer sans crainte que le cerveau humain lui-même, faisant partie du monde matériel, peut être simulé par une machine de Turing. Le reste est à débattre et, du moins à mon avis, sans rapport avec le SDC.

$P \neq NP$$NP-P$$10^{10^{100}}n$$n$$2 \log 10^{10^{100}}$fois plus d'informations à chaque étape de l'algorithme accéléré. Bien entendu, une limite inférieure spécifique serait nécessaire pour garantir l’existence d’un algorithme plus rapide (constantes incluses).

Donc, si vous souhaitez calculer avec précision les problèmes rencontrés par le cerveau humain, compte tenu des contraintes de la vie réelle, telles que les distractions, la capacité d'attention, etc., vous devez définir une limite supérieure pour le nombre total de pas effectués, une limite supérieure pour le nombre d’étapes effectuées consécutivement (même le chercheur le plus dévoué doit dormir et manger), une limitation de l’espace (pas seulement dans la bande, mais aussi dans les registres "internes"), une simulation du comportement de la mémoire car, contrairement aux MT, peut oublier quelque chose que nous écrivons dans notre "bande de travail" ou l'état exact, et bien sûr, déterminer la relation entre les pas de temps de la machine et le temps en secondes ou "pas de cerveau humain". Peut-être que d'autres problèmes surgiraient au fur et à mesure. Ironiquement, un ou plusieurs de ces problèmes ne peuvent pas être résolus par le cerveau humain, du moins efficacement.

${\bf ThC}_0$$\bf{P}$$\bf NC$$\bf \#P$

Si vous donnez à un humain un crayon et du papier, elle peut résoudre presque tous les problèmes en agissant comme une machine. Donc, je pense que cela ne peut pas être le point.

À mon avis, ce qui fait la pensée humaine, c’est l’abstraction, c’est-à-dire que les humains ne dirigent pas les choses (en premier lieu), ils créent des vues sur des choses. Bien que, comme je dois l’admettre, je ne peux fournir aucune théorie presque prête à utiliser pour l’abstraction.

| =

Je réfléchis à cette question depuis longtemps. C’est ce à quoi je suis arrivé:

nous, humains, pensons généralement dans des objets mentaux abstraits et non dans des algorithmes. Les chiffres que nous connaissons, la langue que nous parlons, la pensée était autrefois une idée abstraite. Ces idées ont été étendues par des philosophes, des scientifiques et ensuite mises à profit. Ce que nous avons est différent de leur origine.

Votre question - "Quelle classe de complexité capture le plus précisément la totalité de ce que les êtres humains peuvent accomplir avec leur esprit?" On ne peut répondre à cette question que s’il existe suffisamment de preuves que les êtres humains suivent des modèles mathématiques / algorithmiques / probabilistes. Eh bien, ils pourraient suivre chacune des réponses ci-dessus ou une combinaison de celles-ci. Mais ils sont en réalité quelque chose de différent. Ceci est juste la pensée humaine normale. Décomposer les idées créatives telles que la composition de Mozart, un poème ou la pensée d’un sportif de manière formelle (méthodes de pensée mathématiques / logiques) et tenter de généraliser constituerait un exploit, mais on ne sait pas si cela sera possible.

Je pense aussi que nous pourrions approximer la classe de complexité, mais nous ne pouvons jamais être sûrs.