Welche Komplexitätsklasse ist am engsten mit dem verbunden, was der menschliche Verstand schnell erreichen kann?

Über diese Frage habe ich mich eine Weile gewundert.

Wenn Menschen das P-gegen-NP-Problem beschreiben, vergleichen sie die Klasse NP häufig mit Kreativität. Sie stellen fest, dass das Komponieren einer Symphonie in Mozart-Qualität (analog zu einer NP-Aufgabe) viel schwieriger zu sein scheint, als zu bestätigen, dass eine bereits komponierte Symphonie Mozart-Qualität ist (analog zu einer P-Aufgabe).

Aber ist NP wirklich die "Kreativitätsklasse"? Gibt es nicht viele andere Kandidaten? Es gibt ein altes Sprichwort: "Ein Gedicht wird niemals beendet, sondern nur aufgegeben." Ich bin kein Dichter, aber für mich erinnert dies an die Idee von etwas, für das es keine eindeutige richtige Antwort gibt, die schnell überprüft werden kann. Es erinnert mich mehr an CoNP und Probleme wie TAUTOLOGY als an NP oder SAT. Ich vermute, es ist einfach zu überprüfen, ob ein Gedicht "falsch" ist und verbessert werden muss, aber es ist schwierig zu überprüfen, ob ein Gedicht "richtig" oder "fertig" ist.

In der Tat erinnert mich NP mehr an Logik und linkes Denken als an Kreativität. Beweise, technische Probleme, Sudoku-Rätsel und andere stereotype "Probleme mit der linken Gehirnhälfte" sind vom Qualitätsstandpunkt aus einfacher zu überprüfen als Gedichte oder Musik.

Meine Frage lautet also: Welche Komplexitätsklasse erfasst am genauesten die Gesamtheit dessen, was Menschen mit ihrem Verstand erreichen können? Ich habe mich immer müßig gefragt (und ohne wissenschaftliche Beweise, die meine Spekulationen stützen), ob die linke Gehirnhälfte vielleicht kein ungefährer SAT-Löser ist und die rechte Gehirnhälfte kein ungefährer TAUTOLOGIE-Löser. Vielleicht ist der Geist darauf eingestellt, PH-Probleme zu lösen ... oder er kann sogar PSPACE-Probleme lösen.

Ich habe oben meine Gedanken dargelegt. Ich bin gespannt, ob irgendjemand bessere Einsichten dazu bieten kann. Um meine Frage kurz zu fassen: Ich frage, welche Komplexitätsklasse mit dem verbunden sein soll, was der menschliche Verstand leisten kann, und um Beweise oder ein Argument zu erhalten, das Ihren Standpunkt stützt. Oder, wenn meine Frage schlecht gestellt ist und es keinen Sinn macht, Menschen und Komplexitätsklassen zu vergleichen, warum ist dies der Fall?

Vielen Dank.

Update : Ich habe alles außer dem Titel intakt gelassen, aber hier ist die Frage, die ich wirklich stellen wollte: Welche Komplexitätsklasse ist mit dem verbunden, was der menschliche Verstand schnell erreichen kann ? Was ist "polynomische menschliche Zeit", wenn Sie so wollen? Offensichtlich kann ein Mensch eine Turing-Maschine simulieren, wenn ihm unendlich viel Zeit und Ressourcen zur Verfügung stehen.

Ich vermute, dass die Antwort entweder PH oder PSPACE ist, aber ich kann nicht wirklich ein intelligentes, kohärentes Argument dafür ausdrücken, warum dies der Fall ist.

Beachten Sie auch: Ich interessiere mich hauptsächlich für das, was Menschen annähern oder "die meiste Zeit tun" können. Offensichtlich kann kein Mensch schwierige SAT-Fälle lösen. Wenn der Verstand ein ungefährer X- Solver ist und X für Klasse C vollständig ist, ist das wichtig.

Ich behaupte nicht, dass dies eine vollständige Antwort ist, aber hier sind einige Gedanken, die sich hoffentlich nach dem richten, wonach Sie suchen.

NP entspricht in etwa "Rätseln" (d. H. Der NP-Vollständigkeit von Sudoku, Minesweeper, Free Cell usw., wenn diese Rätsel in geeigneter Weise verallgemeinert werden, um ). PSPACE entspricht "2-Spieler-Spielen" (dh der PSPACE-Vollständigkeit von Schach, Los usw.). Dies ist keine Neuigkeit.$n \to \infty$

Die Leute scheinen im Allgemeinen mit endlichen Instanzen von NP-vollständigen Rätseln klarzukommen, und finden sie dennoch nicht trivial genug, um unterhaltsam zu sein. Die endlichen Instanzen von PSPACE-vollständigen Spielen, die wir spielen, werden als einige der schwierigeren intellektuellen Aufgaben dieser Art angesehen. Dies deutet zumindest darauf hin, dass PSPACE "die Obergrenzen unserer Fähigkeiten erreicht". (Unsere Gegner in diesen PSPACE-vollständigen Spielen sind im Allgemeinen andere Leute. Selbst wenn die Gegner Computer sind, sind die Computer keine perfekten Gegner. Dies führt zu der Frage nach der Macht interaktiver Beweise, wenn die Spieler rechnerisch begrenzt sind. Es gibt auch die technische Tatsache, dass einige Verallgemeinerungen dieser Spiele EXP-vollständig anstelle von PSPACE-vollständig sind.)

Bis zu einem gewissen Grad wurden die Problemgrößen, die bei tatsächlichen Rätseln / Spielen auftreten, auf unsere Fähigkeiten kalibriert. 4x4 Sudoku wäre zu einfach, daher langweilig. 16x16 Sudoku würde zu viel Zeit in Anspruch nehmen (nicht mehr als die Lebensdauer des Universums, aber mehr als die Menschen sind im Allgemeinen bereit, sich zu setzen, um ein Sudoku-Puzzle zu lösen). 9x9 scheint die "Goldlöckchen" -Größe für Leute zu sein, die Sudoku lösen. In ähnlicher Weise scheint es für die meisten Menschen die richtige Schwierigkeit zu sein, Free Cell mit einem Stapel von 4 Farben mit jeweils 13 Karten und 4 freien Zellen zu spielen, um lösbar und dennoch herausfordernd zu sein. (Andererseits ist eine der klügsten Personen, die ich kenne, in der Lage, Free Cell-Spiele so zu lösen, als würde sie nur die natürlichen Zahlen "1,2,3,4, ..." zählen.) Ähnliches gilt für die Größe von Go und Chess Bretter.

Haben Sie jemals versucht, eine 6x6-Permanent von Hand zu berechnen?

Ich nehme an, der Punkt ist, dass, wenn Sie natürliche Probleme in Klassen nehmen, die deutlich über PSPACE (oder EXP) liegen, die einzigen endlichen Fälle, die Menschen lösen können, so klein erscheinen, dass sie uninteressant sind. Ein Teil des Grundes, warum "natürlich" hier notwendig ist, ist, dass man ein natürliches Problem annehmen und dann alle Instanzen der Größe "unnatürlich" modifizieren kann, so dass für alle Instanzen ein Mensch jemals versuchen würde, das Problem völlig unlösbar zu machen. unabhängig von seiner asymptotischen Komplexität.$< 10^{10}$

Umgekehrt besteht bei Problemen mit EXP die Möglichkeit, dass jede Problemgröße unterhalb der "Ferse des Exponentials" von den meisten Menschen in angemessener Zeit lösbar ist.

Was den Rest der PH betrifft, gibt es nicht viele (irgendwelche?) Natürlichen Spiele, die mit einer festgelegten Anzahl von Runden gespielt werden. Dies hängt auch damit zusammen, dass wir nicht viele natürliche Probleme kennen, die bei PH-Werten über dem dritten auftreten.

Wie von Serge erwähnt, spielt FPT hier eine Rolle, aber (glaube ich) hauptsächlich in der Tatsache, dass einige Probleme natürlich mehr als eine "Eingabegröße" haben.

Die Tractable Cognition-These postuliert, dass die menschlichen kognitiven Fähigkeiten durch die rechnerische Traktierbarkeit eingeschränkt werden. Auf diese Weise verwendet die P-Cognition-These die deterministische Polynomzeit als Modell für die rechnerische Traktierbarkeit, während in der folgenden Abhandlung argumentiert wird, dass die FPT-Cognition-These angemessener ist. In Iris van Rooijs Artikel in der Juni-Ausgabe 2009 des Parametrized Complexity Newsletters finden Sie ausführlichere Informationen und Hinweise auf andere Veröffentlichungen.

• Iris van Rooij. Die Tractable Cognition-These . Cognitive Science, 32, S. 939–984, 2008.
• Iris van Rooij. Parameter, die Cognitive Work Light machen. FPT News: Parametrisierter Komplexitäts-Newsletter, Juni 2009 .

Ich denke, man wird zum falschen Modell geführt, indem man versucht, aus den Dingen zu extrapolieren, die das menschliche Gehirn zu berechnen scheint, und ich denke, es wäre besser, die entgegengesetzte Ansicht zu vertreten und stattdessen aus dem Rechenmodell zu extrapolieren, das es ist.

Für mich ist die Komplexitätsklasse, die den menschlichen Verstand am sinnvollsten erfasst, die Klasse ungleichmäßige Schaltkreise . Diese Ansicht wird durch die Modellierung der Funktionsweise des Gehirns als neuronales Netzwerk unterstützt, das Berechnungen in einem Augenblick durchführt.$TC^0$

Auch stimme ich der Aussage in der Frage, dass der menschliche Verstand eine Turing-Maschine simulieren kann, nicht zu. Vielmehr kann es die endliche Steuerung der Turing-Maschine simulieren . Um sehr komplizierte Aufgaben ausführen zu können, scheint es notwendig zu sein, Informationen auf einem "Band" aufzuzeichnen.

Komplexitätsklassen werden als asymptotische Komplexität definiert, daher lassen sie sich nicht gut auf die kognitiven Fähigkeiten des Menschen abbilden, die notwendigerweise auf begrenzte Problemgrößen beschränkt sind.

Die Faustregel lautet: Wenn etwas für einen Computer einfach ist, kann es für einen Menschen schwierig sein, und umgekehrt, wenn es für einen Computer schwierig ist, kann es für einen Menschen einfach sein.

"Easy / hard for a computer" bezieht sich hier auf die praktische Handhabbarkeit, nicht auf eine abstrakte Komplexitätsklasse.

Zum Beispiel ist das Aufsummieren einer Liste von 1 Milliarde Ganzzahlen für einen modernen Computer einfach und für einen Menschen schwierig, während das Erstellen einer verbalen Beschreibung eines Bildes für einen Menschen einfach, für einen Computer jedoch schwierig (derzeit im Allgemeinen unmöglich) ist.

Untersuchungen der künstlichen Intelligenz haben gezeigt, dass viele kognitive Aufgaben, die Menschen und Tiere leicht, in einigen Fällen sogar unbewusst ausführen, als NP-harte Probleme modelliert werden können. Menschen sind nicht in der Lage, für alle Größen optimale Lösungen für diese Probleme zu finden, aber sie sind in der Lage, heuristische Lösungen für praktische Größen zu finden, die viel besser sind als die bekanntesten AI-Algorithmen.

Beachten Sie auch, dass die erwähnte Unterscheidung zwischen linker und rechter Gehirnhälfte zu simpel und obsolet ist. Die Lateralisierung der Gehirnfunktionen ist viel subtiler und kann sogar von Individuum zu Individuum unterschiedlich sein.

Wenn wir uns dafür entscheiden, das menschliche Gehirn selbst zu untersuchen, anstatt wie Menschen ihr Gehirn zur Lösung von Problemen verwenden, dann glaube ich nicht, dass dies ein Problem der Komplexität ist, sondern der Berechenbarkeit. Da jedes TM eine Übergangsfunktion benötigt, kann ein Mensch die Schritte des TM imitieren, daher ist das menschliche Gehirn Turing-vollständig.

Können TMs in umgekehrter Richtung alles berechnen, was Menschen tun? Die kurze Antwort lautet: Wir wissen es nicht. Unter der Annahme, dass die These von Church-Turing wahr ist, hängt es von Ihrer Sicht auf die Welt (philosophisch, spirituell, religiös und andere) ab, ob sich die Antwort ändert oder nicht. In diesem Fall können wir mit Sicherheit sagen, dass das menschliche Gehirn selbst als Teil der materiellen Welt von einer Turing-Maschine simuliert werden kann. Der Rest steht zur Debatte und hat, zumindest meiner Meinung nach, nichts mit TCS zu tun.

Man könnte argumentieren, dass wenn alle Probleme in ein Leben lang in den würden. Aber wir sprechen über die Kraft des Gehirns. Die Übergangstabelle und das Arbeitsband könnten von Generation zu Generation weitergegeben werden, bis die Antwort gelöst ist. Selbst wenn wir fordern, dass von Menschen lösbare Probleme die Lebensdauer einer einzelnen Person nicht überschreiten, werden , was nur linear ist, scheint machbar zu sein? Ich denke nicht. Man kann argumentieren, dass es ein TM gibt, das dasselbe in nur Verwendung des Beschleunigungssatzes tut , das aber das Speichern von erfordern würde.N P - P 10 10 100 n n 2 log 10 10 $P \neq NP$$NP-P$$10^{10^{100}}n$$n$$2 \log 10^{10^{100}}$Mal mehr Informationen in jedem Schritt des beschleunigten Algorithmus. Natürlich wäre eine bestimmte Untergrenze erforderlich, um sicherzustellen, dass es keinen schnelleren Algorithmus (einschließlich Konstanten) gibt.

Wenn Sie also genau berechnen möchten, welche Probleme das menschliche Gehirn aufgrund der Einschränkungen des tatsächlichen Lebens, wie Ablenkungen, Aufmerksamkeitsspanne usw., hat, sollten Sie eine Obergrenze für die Anzahl der insgesamt ausgeführten Schritte und eine Obergrenze für die Anzahl der Schritte, die nacheinander ausgeführt werden (selbst der engagierteste Forscher muss schlafen und essen), Begrenzung des Platzes (nicht nur auf dem Band, sondern auch in "internen" Registern), Simulation der Funktionsweise des Gedächtnisses, da TMs anders sind als wir Ich kann etwas vergessen, das wir in unser "Arbeitsband" geschrieben haben, oder den genauen Zustand, und natürlich das Verhältnis zwischen Zeitschritten der Maschine und Zeit in Sekunden oder "menschlichen Gehirnschritten" bestimmen. Vielleicht tauchen andere Probleme auf, wenn Sie gehen. In einer ironischen Wendung können vielleicht eines oder mehrere dieser Probleme vom menschlichen Gehirn zumindest nicht effizient gelöst werden.

Nun, ist die Klasse von Funktionen, die ein (polynomiales) neuronales Netz in konstanter Zeit lösen kann. In der Polynomzeit konnte genau und in der Polylogzeit . Aber vielleicht sollten wir exponentiell viele Neuronen und Polynomzeiten zulassen? Ich glaube, das ergibt die Zählhierarchie, die über . Die Anzahl der Hierarchieebenen ist meines Erachtens die Häufigkeit, mit der ein Neuron seine Fähigkeit nutzt, einen exponentiellen Zufluss zu haben.P NC#${\bf ThC}_0$$\bf{P}$$\bf NC$$\bf \#P$

Wenn Sie einem Menschen Bleistift und Papier geben, kann er fast jedes Problem lösen, indem er sich wie eine Maschine verhält. Ich denke, das kann nicht der Punkt sein.

Imho, was menschliches Denken ausmacht, ist Abstraktion, dh Menschen führen Dinge nicht (an erster Stelle) aus, sie schaffen Ansichten über Dinge. Obwohl ich, wie ich zugeben muss, keine annähernd gebrauchsfertige Theorie für die Abstraktion vorlegen kann.

| =

Ich habe lange über diese Frage nachgedacht. Dazu bin ich gekommen:

Wir Menschen denken normalerweise in abstrakten mentalen Objekten und nicht in Algorithmen. Die Zahlen, die wir kennen, die Sprache, die wir sprechen, das Denken war einmal eine abstrakte Idee. Diese Ideen wurden von Philosophen, Wissenschaftlern erweitert und dann in die Tat umgesetzt. Was wir haben, ist anders als ihre Entstehung.

Ihre Frage - "Welche Komplexitätsklasse erfasst am genauesten die Gesamtheit dessen, was Menschen mit ihrem Verstand erreichen können?" kann nur beantwortet werden, wenn genügend Beweise dafür vorliegen, dass Menschen mathematischen / algorithmischen / probabilistischen Modellen folgen. Nun, sie könnten jeder der oben genannten oder einer Kombination davon folgen. Aber sie sind tatsächlich etwas anderes. Dies ist nur normales menschliches Denken. Die kreativen Gedanken wie Mozarts Komposition, ein Gedicht oder das Denken eines Sportlers auf jeweils formale Weise (mathematisch / logische Methoden seines Denkens) aufzuschlüsseln und zu verallgemeinern, wäre eine ziemliche Leistung, nicht sicher, ob das überhaupt möglich sein wird.

Ich denke auch, dass wir uns der Komplexitätsklasse annähern könnten, aber wir können nie sicher sein.