Jaka klasa złożoności jest najbardziej związana z tym, co ludzki umysł może szybko osiągnąć?

Zastanawiam się nad tym pytaniem.

Kiedy ludzie opisują problem P vs. NP, często porównują NP klasy do kreatywności. Zauważają, że skomponowanie symfonii jakości Mozarta (analogicznej do zadania NP) wydaje się znacznie trudniejsze niż sprawdzenie, czy już skomponowana symfonia ma jakość Mozarta (analogiczną do zadania P).

Ale czy NP to naprawdę „klasa kreatywności”? Czy nie ma wielu innych kandydatów? Jest takie stare powiedzenie: „Wiersz nigdy nie jest skończony, tylko porzucony”. Nie jestem poetą, ale dla mnie przypomina to ideę czegoś, na co nie ma jednoznacznej właściwej odpowiedzi, którą można by szybko zweryfikować ... przypomina mi bardziej CONP i problemy takie jak TAUTOLOGIA niż NP czy SAT. Chodzi mi o to, że łatwo jest zweryfikować, kiedy wiersz jest „zły” i wymaga poprawy, ale trudny do zweryfikowania, gdy wiersz jest „poprawny” lub „skończony”.

Rzeczywiście, NP przypomina mi bardziej logikę i lewostronne myślenie niż kreatywność. Dowody, problemy inżynieryjne, łamigłówki sudoku i inne stereotypowo „lewostronne problemy” są bardziej NP i łatwe do zweryfikowania z punktu widzenia jakości niż poezji czy muzyki.

Moje pytanie brzmi zatem: która klasa złożoności najdokładniej uchwyci całość tego, co ludzie mogą osiągnąć za pomocą swoich umysłów? Zawsze zastanawiałem się leniwie (i bez dowodów naukowych na poparcie moich spekulacji), czy być może lewy mózg nie jest przybliżonym narzędziem do rozwiązywania problemów SAT, a prawy mózg nie jest przybliżonym narzędziem do rozwiązywania problemów TAUTOLOGY. Być może umysł jest skonfigurowany do rozwiązywania problemów z PH ... a może może nawet rozwiązać problemy z PSPACE.

Przedstawiłem swoje myśli powyżej; Jestem ciekawy, czy ktokolwiek może zaoferować lepszy wgląd w to. Mówiąc zwięźle: pytam, która klasa złożoności powinna być powiązana z tym, co ludzki umysł może osiągnąć, oraz o dowody lub argument wspierający twój punkt widzenia. Lub, jeśli moje podejście jest niewłaściwe i nie ma sensu porównywanie ludzi i klas złożoności, dlaczego tak jest?

Dzięki.

Aktualizacja : Pozostawiłem wszystko oprócz tytułu nienaruszone powyżej, ale oto pytanie, które naprawdę chciałem zadać: która klasa złożoności jest powiązana z tym, co ludzki umysł może szybko osiągnąć ? Czym jest „wielomianowy czas ludzki”, jeśli chcesz? Oczywiście człowiek może symulować maszynę Turinga, mając nieskończony czas i zasoby.

Podejrzewam, że odpowiedź brzmi PH lub PSPACE, ale tak naprawdę nie jestem w stanie sformułować inteligentnego, spójnego argumentu przemawiającego za tym, dlaczego tak jest.

Uwaga: Interesuje mnie głównie to, co ludzie mogą przybliżyć lub „zrobić przez większość czasu”. Oczywiście żaden człowiek nie jest w stanie rozwiązać trudnych przypadków SAT. Jeśli umysł jest przybliżonym X- solwerem, a X jest kompletny dla klasy C , to ważne.

Nie twierdzę, że jest to kompletna odpowiedź, ale oto kilka myśli, które, mam nadzieję, są zgodne z tym, czego szukasz.

$n \to \infty$

Ludzie na ogół wydają się radzić sobie ze skończonymi przypadkami układanek NP-zupełnych, a mimo to uważają je za wystarczająco trywialne, by były zabawne. Skończone przypadki gier pełnych PSPACE, w które gramy, są uważane za niektóre z trudniejszych zadań intelektualnych tego typu. To przynajmniej sugeruje, że PSPACE „osiąga górne granice” naszych możliwości. (Jednak naszymi przeciwnikami w tych grach kompletnych z PSPACE są na ogół inni ludzie. Nawet gdy przeciwnicy są komputerami, komputery nie są idealnymi przeciwnikami. To zmierza w kierunku mocy interaktywnych dowodów, gdy gracze są ograniczeni obliczeniowo. Istnieje także techniczność, że niektóre uogólnienia tych gier są EXP-complete zamiast PSPACE-complete.)

Do pewnego stopnia rozmiary problemów pojawiające się w rzeczywistych łamigłówkach / grach zostały skalibrowane do naszych możliwości. Sudoku 4x4 byłoby zbyt łatwe, dlatego nudne. Sudoku 16x16 zajęłoby zbyt dużo czasu (nie więcej niż czas życia wszechświata, ale więcej niż ludzie są zazwyczaj gotowi usiąść, aby rozwiązać zagadkę Sudoku). 9x9 wydaje się być wielkością „Złotowłosa” dla osób rozwiązujących Sudoku. Podobnie, granie w Free Cell z talią 4 kolorów po 13 kart i 4 wolne komórki wydaje się być na odpowiednim poziomie trudności do rozwiązania, ale stanowi wyzwanie dla większości ludzi. (Z drugiej strony, jedna z najmądrzejszych osób, które znam, jest w stanie rozwiązywać gry Free Cell tak, jakby liczyły tylko liczby naturalne „1,2,3,4, ...”) Podobnie dla wielkości Go i Chess tablice.

Czy kiedykolwiek próbowałeś ręcznie obliczyć wartość stałą 6x6?

$< 10^{10}$

I odwrotnie, w przypadku problemów w EXP każdy rozmiar problemu poniżej „pięty wykładniczej” ma szansę być rozwiązany przez większość ludzi w rozsądnym czasie.

Jeśli chodzi o resztę PH, nie ma wielu (żadnych?) Naturalnych gier, w które grają ludzie z określoną liczbą rund. Jest to również w jakiś sposób związane z faktem, że nie znamy wielu naturalnych problemów zakończonych dla poziomów PH powyżej trzeciego.

Jak wspomniał Serge, FPT ma tu do odegrania pewną rolę, ale (myślę) głównie dlatego, że niektóre problemy mają oczywiście więcej niż jeden „rozmiar wejściowy”.

Teza tractable Cognition postuluje, że zdolności poznawcze człowieka są ograniczane przez obliczeniowej ustępliwość. W ten sposób teza P-Cognition wykorzystuje deterministyczny czas wielomianowy jako model podatności na obliczenia, podczas gdy w poniższym artykule argumentuje się, że teza FPT-Cognition jest bardziej odpowiednia. Zobacz artykuł Iris van Rooij w wydaniu Parameterized Complexity Newsletter z czerwca 2009 r., Aby uzyskać bardziej szczegółową dyskusję i wskazówki do innych artykułów.

• Iris van Rooij. Teza możliwego do poznania . Cognitive Science, 32, s. 939–984, 2008.
• Iris van Rooij. Parametry, które sprawiają, że Cognitive Work Light. Wiadomości FPT: biuletyn o parametrach złożoności, czerwiec 2009 r .

Myślę, że prowadzi się do niewłaściwego modelu poprzez próbę ekstrapolacji z tego, co ludzki mózg wydaje się obliczać, i myślę, że lepiej byłoby przyjąć przeciwny pogląd i zamiast tego dokonać ekstrapolacji z modelu obliczeniowego.

$TC^0$

Nie zgadzam się również ze stwierdzeniem w pytaniu, że ludzki umysł może symulować maszynę Turinga. Zamiast tego może symulować skończoną kontrolę maszyny Turinga. Aby wykonywać bardzo skomplikowane zadania, wydaje się konieczne, aby móc nagrywać informacje na „taśmie”.

Klasy złożoności są zdefiniowane w kategoriach złożoności asymptotycznej, dlatego nie odwzorowują dobrze zdolności poznawczych ludzi, które z konieczności są ograniczone do ograniczonych rozmiarów problemów.

Ogólna zasada brzmi: jeśli coś jest łatwe dla komputera, to może być trudne dla człowieka i odwrotnie, jeśli jest trudne dla komputera, może być łatwe dla człowieka.

Tutaj „łatwy / trudny dla komputera” odnosi się do praktycznej wykonalności, a nie abstrakcyjnej klasy złożoności.

Na przykład zebranie listy 1 miliarda liczb całkowitych jest łatwe dla współczesnego komputera i trudne dla człowieka, podczas gdy stworzenie ustnego opisu obrazu jest łatwe dla człowieka, ale trudne (obecnie w ogólnym przypadku niemożliwe) dla komputera.

Badania nad sztuczną inteligencją wykazały, że wiele zadań poznawczych, które ludzie i zwierzęta wykonują łatwo, w niektórych przypadkach nawet podświadomie, można modelować jako problemy trudne NP. Ludzie nie są w stanie znaleźć optymalnych rozwiązań tych problemów dla wszystkich rozmiarów, ale są w stanie znaleźć heurystyczne rozwiązania dla praktycznych rozmiarów znacznie lepiej niż najbardziej znane algorytmy AI.

Zauważ też, że wspomniane rozróżnienie między lewym a prawym mózgiem jest zbyt uproszczone i przestarzałe. Lateralizacja funkcji mózgu jest znacznie bardziej subtelna i może nawet różnić się u poszczególnych osób.

Jeśli zdecydujemy się badać sam mózg ludzki, a nie sposób, w jaki ludzie używają go do rozwiązywania problemów, nie sądzę, że jest to kwestia złożoności, ale raczej obliczalności. Ponieważ każda TM potrzebuje funkcji przejścia, człowiek może naśladować kroki TM, dlatego ludzki mózg jest kompletny w Turinga.

Czy w odwrotnym kierunku TM mogą obliczyć wszystko, co robią ludzie? Krótka odpowiedź brzmi: nie wiemy. Zakładając, że teza Kościoła-Turinga jest prawdziwa, to czy odpowiedź się zmieni, czy nie, zależy od twojego spojrzenia na świat (filozoficzny, duchowy, religijny i inny). W takim przypadku możemy śmiało powiedzieć, że sam mózg ludzki jako część świata materialnego może być symulowany przez maszynę Turinga. Reszta jest przedmiotem debaty i, przynajmniej moim zdaniem, nie jest związana z TCS.

$P \neq NP$$NP-P$$10^{10^{100}}n$$n$$2 \log 10^{10^{100}}$razy więcej informacji na każdym etapie przyspieszonego algorytmu. Oczywiście potrzebna byłaby określona dolna granica, aby zapewnić, że szybszy algorytm (łącznie ze stałymi) nie istnieje.

Tak więc, jeśli chcesz dokładnie obliczyć, jakie problemy ma ludzki mózg, biorąc pod uwagę ograniczenia rzeczywistego życia, takie jak rozproszenie uwagi, zasięg uwagi itp., Powinieneś mieć górną granicę całkowitej liczby kroków wykonanych, górną granicę liczba kroków wykonanych kolejno (nawet najbardziej oddany badacz musi spać i jeść), ograniczenie przestrzeni (nie tylko na taśmie, ale także w „wewnętrznych” rejestrach), symulacja działania pamięci, ponieważ w przeciwieństwie do baz TM może zapomnieć o czymś, co piszemy na „taśmie roboczej” lub dokładnym stanie, i oczywiście określić związek między krokami czasu maszyny i czasem w sekundach lub „krokami ludzkiego mózgu”. Być może pojawią się inne problemy, które pojawią się. Jak na ironię, jeden lub więcej z tych problemów nie może być rozwiązany przez ludzki mózg, przynajmniej skutecznie.

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

Jeśli dasz człowiekowi ołówek i papier, może rozwiązać prawie każdy problem, zachowując się jak maszyna. Myślę więc, że nie o to chodzi.

Imho sprawia, że ​​ludzkie myślenie jest abstrakcją, tzn. Ludzie nie rządzą (przede wszystkim), tworzą poglądy na różne rzeczy. Chociaż, jak muszę przyznać, nie mogę podać prawie gotowej do użycia teorii do abstrakcji.

| =

Długo zastanawiałem się nad tym pytaniem. Do tego doszedłem:

my, ludzie, myślimy zwykle w abstrakcyjnych obiektach mentalnych, a nie w algorytmach. Liczby, które znamy, język, którym mówimy, myślenie było kiedyś abstrakcyjnym pomysłem. Idee te zostały rozszerzone przez filozofów, naukowców, a następnie wykorzystane. To, co mamy, różni się od tego, jak powstały.

Twoje pytanie - „Która klasa złożoności najdokładniej oddaje całość tego, co ludzie mogą osiągnąć dzięki swoim umysłom?” można odpowiedzieć tylko wtedy, gdy istnieje wystarczający dowód, że ludzie stosują modele matematyczne / algorytmiczne / probabilistyczne. Cóż, mogą śledzić każdą z powyższych lub ich kombinację. Ale w rzeczywistości są czymś innym. To jest po prostu normalne ludzkie myślenie. Przełamanie twórczych myśli, takich jak kompozycja Mozarta, wiersz lub myślenie sportowca na odpowiednie formalne sposoby (matematyczne / logiczne metody ich myślenia) i próba uogólnienia byłyby nie lada wyczynem, nie jestem jednak pewien, czy to będzie możliwe.

Myślę też, że moglibyśmy przybliżyć klasę złożoności, ale nigdy nie możemy być pewni.