Apa kelas kompleksitas yang paling erat terkait dengan apa yang dapat dicapai oleh pikiran manusia dengan cepat?

Pertanyaan ini adalah sesuatu yang sudah lama saya tanyakan.

Ketika orang menggambarkan masalah P vs NP, mereka sering membandingkan NP kelas dengan kreativitas. Mereka mencatat bahwa menyusun simfoni kualitas Mozart (analog dengan tugas NP) tampaknya jauh lebih sulit daripada memverifikasi bahwa simfoni yang sudah dikomposisikan adalah kualitas Mozart (yang dianalogikan dengan tugas P).

Tetapi apakah NP benar-benar "kelas kreativitas?" Apakah tidak ada banyak kandidat lain? Ada pepatah lama: "Puisi tidak pernah selesai, hanya ditinggalkan." Saya bukan penyair, tetapi bagi saya, ini mengingatkan pada gagasan tentang sesuatu yang tidak ada jawaban benar yang pasti yang dapat diverifikasi dengan cepat ... ini mengingatkan saya pada lebih banyak tentang coNP dan masalah seperti TAUTOLOGI daripada NP atau SAT. Saya kira yang saya maksudkan adalah mudah untuk memverifikasi ketika sebuah puisi "salah" dan perlu diperbaiki, tetapi sulit untuk memverifikasi ketika sebuah puisi "benar" atau "selesai."

Memang, NP lebih mengingatkan saya pada logika dan pemikiran otak kiri daripada kreativitas. Bukti, masalah teknik, teka-teki Sudoku, dan "masalah otak kiri" stereotip lainnya lebih NP dan mudah diverifikasi dari sudut pandang kualitas daripada dari puisi atau musik.

Jadi, pertanyaan saya adalah: Kelas kompleksitas mana yang paling tepat menangkap totalitas apa yang dapat dicapai oleh manusia dengan pikiran mereka? Saya selalu bertanya-tanya iseng (dan tanpa bukti ilmiah untuk mendukung spekulasi saya) apakah mungkin otak kiri bukan pemecah SAT-perkiraan, dan otak kanan bukanlah pemecah TAUTOLOGI perkiraan. Mungkin pikiran diatur untuk menyelesaikan masalah PH ... atau mungkin bahkan dapat memecahkan masalah PSPACE.

Saya telah menawarkan pemikiran saya di atas; Saya ingin tahu apakah ada yang bisa menawarkan wawasan yang lebih baik tentang ini. Untuk menyatakan pertanyaan saya dengan singkat: Saya bertanya kelas kompleksitas mana yang harus dikaitkan dengan apa yang dapat dicapai oleh pikiran manusia, dan untuk bukti atau argumen yang mendukung sudut pandang Anda. Atau, jika pertanyaan saya salah dan tidak masuk akal untuk membandingkan manusia dan kelas kompleksitas, mengapa demikian?

Terima kasih.

Pembaruan : Saya telah meninggalkan segalanya kecuali judulnya tetap di atas, tetapi inilah pertanyaan yang ingin saya tanyakan: Kelas kompleksitas mana yang dikaitkan dengan apa yang dapat dicapai oleh pikiran manusia dengan cepat ? Apa itu "waktu manusia polinomial," jika Anda mau? Jelas, manusia dapat mensimulasikan mesin Turing yang diberikan waktu dan sumber daya tak terbatas.

Saya menduga bahwa jawabannya adalah PH atau PSPACE, tetapi saya tidak dapat benar-benar mengartikulasikan argumen yang cerdas dan koheren mengapa ini terjadi.

Catatan juga: Saya terutama tertarik pada apa yang dapat diperkirakan oleh manusia atau "melakukan sebagian besar waktu." Jelas, tidak ada manusia yang bisa menyelesaikan contoh keras SAT. Jika pikiran adalah perkiraan X- solver, dan X lengkap untuk kelas C , itu penting.

Saya tidak mengklaim ini adalah jawaban yang lengkap, tetapi di sini ada beberapa pemikiran yang diharapkan sesuai dengan apa yang Anda cari.

$n \to \infty$

Orang-orang pada umumnya tampak baik-baik saja dengan contoh teka-teki lengkap NP yang terbatas, namun menganggapnya tidak cukup sepele untuk menghibur. Contoh terbatas dari game PSPACE-complete yang kami mainkan dianggap sebagai beberapa tugas intelektual yang lebih sulit dari jenis ini. Ini setidaknya menunjukkan bahwa PSPACE "memukul batas atas" kemampuan kita. (Namun lawan kami dalam game PSPACE-complete ini umumnya adalah orang lain. Bahkan ketika lawannya adalah komputer, komputer itu bukan lawan yang sempurna. Ini mengarah pada pertanyaan tentang kekuatan bukti interaktif ketika para pemain memiliki keterbatasan komputasi. Ada juga teknis bahwa beberapa generalisasi dari game-game ini adalah EXP-complete daripada PSPACE-complete.)

Sampai batas tertentu, ukuran masalah yang muncul pada puzzle / game yang sebenarnya telah dikalibrasi sesuai kemampuan kita. 4x4 Sudoku akan terlalu mudah, karenanya membosankan. 16x16 Sudoku akan memakan terlalu banyak waktu (tidak lebih dari masa kehidupan alam semesta, tetapi lebih dari orang-orang pada umumnya bersedia duduk untuk memecahkan teka-teki Sudoku). 9x9 tampaknya menjadi ukuran "Goldilocks" untuk orang yang memecahkan Sudoku. Demikian pula, memainkan Free Cell dengan set kartu yang terdiri dari 13 kartu masing-masing dan 4 sel bebas tampaknya merupakan kesulitan yang tepat untuk dipecahkan namun menantang bagi kebanyakan orang. (Di sisi lain, salah satu orang terpintar yang saya tahu mampu menyelesaikan permainan Sel Gratis seolah-olah dia hanya menghitung angka alami "1,2,3,4, ...") Demikian pula untuk ukuran Go dan Chess papan.

Pernahkah Anda mencoba menghitung 6x6 permanen dengan tangan?

$< 10^{10}$

Sebaliknya, untuk masalah dalam EXP, ukuran masalah apa pun di bawah "tumit eksponensial" memiliki peluang untuk dipecahkan oleh kebanyakan orang dalam jumlah waktu yang wajar.

Mengenai PH lainnya, tidak banyak (ada?) Permainan alami yang dimainkan orang dengan jumlah putaran yang tetap. Ini entah bagaimana juga terkait dengan fakta bahwa kita tidak tahu banyak masalah alami yang lengkap untuk level PH di atas yang ketiga.

Seperti disebutkan oleh Serge, FPT memiliki peran untuk dimainkan di sini, tetapi (saya pikir) sebagian besar pada kenyataan bahwa beberapa masalah secara alami memiliki lebih dari satu "ukuran input" yang terkait dengannya.

The penurut Kognisi tesis mendalilkan bahwa kapasitas kognitif manusia dibatasi oleh tractability komputasi. Dengan cara ini, tesis P-Cognition menggunakan waktu polinomial deterministik sebagai model untuk traktabilitas komputasi, sedangkan dalam makalah di bawah ini, dikemukakan bahwa tesis FPT-Cognition lebih tepat. Lihat artikel Iris van Rooij dalam Newsletter Parameterized Complexity Newsletter edisi Juni 2009 untuk diskusi yang lebih terperinci dan petunjuk ke makalah lain.

• Iris van Rooij. Tesis Cactition Cactition . Cognitive Science, 32, hlm. 939-984, 2008.
• Iris van Rooij. Parameter yang membuat Cognitive Work Light. Berita FPT: Newsletter Kompleksitas Parameter, Juni 2009 .

Saya pikir seseorang mengarah ke model yang salah dengan mencoba mengekstrapolasi dari hal-hal yang tampaknya dikomputasi oleh otak manusia, dan saya pikir akan lebih baik untuk mengambil pandangan yang berlawanan dan bukannya mengekstrapolasi dari model komputasi itu.

$TC^0$

Juga, saya tidak setuju dengan pernyataan dalam pertanyaan bahwa pikiran manusia dapat mensimulasikan mesin Turing. Sebaliknya, yang dapat dilakukannya adalah mensimulasikan kontrol hingga dari mesin Turing. Untuk melakukan tugas yang sangat rumit, tampaknya perlu untuk merekam informasi pada "kaset".

Kelas kompleksitas didefinisikan dalam hal kompleksitas asimptotik, oleh karena itu mereka tidak memetakan dengan baik kemampuan kognitif manusia, yang tentu terbatas pada ukuran masalah yang terbatas.

Aturan praktisnya adalah: jika sesuatu itu mudah untuk komputer, maka mungkin sulit bagi manusia, sebaliknya, jika sulit untuk komputer mungkin mudah bagi manusia.

Di sini "mudah / sulit untuk komputer" mengacu pada kemudahan penelusuran praktis, bukan kelas kompleksitas abstrak.

Misalnya, menambahkan daftar 1 miliar bilangan bulat mudah untuk komputer modern dan sulit bagi manusia, sambil menghasilkan deskripsi verbal gambar mudah bagi manusia tetapi sulit (saat ini tidak mungkin dalam kasus umum) untuk komputer.

Penelitian Kecerdasan Buatan menunjukkan bahwa banyak tugas kognitif yang dilakukan manusia dan hewan dengan mudah, dalam beberapa kasus bahkan secara tidak sadar, dapat dimodelkan sebagai masalah NP-hard. Manusia tidak dapat menemukan solusi optimal untuk masalah ini untuk semua ukuran, tetapi mereka dapat menemukan solusi heuristik untuk ukuran praktis yang jauh lebih baik daripada algoritma AI yang paling dikenal.

Juga perhatikan bahwa perbedaan otak kiri vs otak kanan yang Anda sebutkan terlalu sederhana dan usang. Lateralisasi fungsi otak jauh lebih halus, dan bahkan dapat bervariasi dari satu orang ke orang lain.

Jika kita memilih untuk mempelajari otak manusia itu sendiri daripada bagaimana manusia menggunakan otak mereka untuk menyelesaikan masalah, saya tidak percaya ini adalah masalah kompleksitas, tetapi lebih dari komputabilitas. Karena setiap TM membutuhkan fungsi transisi, manusia dapat meniru langkah-langkah TM, oleh karena itu, otak manusia adalah Turing-complete.

Di arah sebaliknya, dapatkah TM menghitung semua yang dilakukan manusia? Jawaban singkatnya adalah kita tidak tahu. Dengan asumsi bahwa tesis Gereja-Turing benar, apakah jawabannya akan berubah atau tidak tergantung pada pandangan Anda tentang dunia (filosofis, spiritual, religius dan lainnya). Dalam hal itu, kita dapat dengan aman mengatakan bahwa otak manusia itu sendiri sebagai bagian dari dunia material, dapat disimulasikan oleh mesin Turing. Sisanya terserah debat dan, setidaknya menurut saya, tidak terkait TCS.

$P \neq NP$$NP-P$$10^{10^{100}}n$$n$$2 \log 10^{10^{100}}$kali lebih banyak informasi di setiap langkah dari algoritma dipercepat. Tentu saja, batas bawah spesifik akan diperlukan untuk memastikan algoritma yang lebih cepat (termasuk konstanta) tidak ada.

Jadi, jika Anda ingin menghitung dengan tepat masalah apa yang terjadi pada otak manusia, mengingat kendala kehidupan yang sebenarnya, seperti gangguan, rentang perhatian, dll. Anda harus memiliki batas atas pada jumlah langkah yang dilakukan secara total, batas atas pada sejumlah langkah yang dilakukan secara berurutan (bahkan peneliti yang paling setia harus tidur dan makan), batasan pada ruang (tidak hanya dalam rekaman, tetapi juga dalam register "internal"), simulasi bagaimana memori bertindak karena tidak seperti TM, kami dapat melupakan sesuatu yang kita tulis di "pita kerja" kami atau keadaan tepatnya, dan tentu saja, menentukan hubungan antara langkah waktu mesin dan waktu dalam detik atau "langkah otak manusia". Mungkin masalah lain akan muncul saat Anda pergi. Dalam putaran ironis, mungkin satu atau lebih dari masalah ini tidak dapat diselesaikan oleh otak manusia, setidaknya secara efisien.

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

Jika Anda memberi manusia pensil dan kertas, dia dapat memecahkan hampir semua masalah, dengan bertindak seperti mesin. Jadi saya pikir ini bukan intinya.

Seperti apa yang membuat pemikiran manusia adalah abstraksi, yaitu manusia tidak menjalankan sesuatu (sejak awal), mereka menciptakan pandangan tentang hal-hal. Meskipun, seperti yang harus saya akui, saya tidak bisa memberikan teori yang hampir siap untuk digunakan untuk abstraksi.

| =

Saya sudah lama memikirkan pertanyaan ini. Inilah yang saya

pikirkan : Kita manusia biasanya berpikir dalam objek mental abstrak dan bukan dalam algoritma. Angka-angka yang kita tahu, bahasa yang kita gunakan, pemikiran itu dulunya adalah gagasan abstrak. Ide-ide ini dikembangkan oleh para filsuf, ilmuwan dan kemudian digunakan. Apa yang kita miliki berbeda dari bagaimana mereka berasal.

Pertanyaan Anda - "Kelas kompleksitas mana yang paling tepat menangkap totalitas apa yang dapat dicapai manusia dengan pikiran mereka?" hanya dapat dijawab jika ada cukup bukti bahwa manusia mengikuti model matematika / algoritmik / probabilistik. Yah, mereka mungkin mengikuti masing-masing di atas atau kombinasi mereka. Tetapi mereka sebenarnya adalah sesuatu yang berbeda. Ini hanya pemikiran manusia normal. Mengurai pemikiran kreatif seperti komposisi Mozart, puisi atau pemikiran olahragawan dengan cara formal masing-masing (metode matematika / logis dari pemikiran mereka) dan mencoba untuk menggeneralisasi akan menjadi suatu prestasi, tidak yakin apakah itu akan mungkin terjadi.

Saya juga berpikir kita mungkin mendekati kelas kompleksitas, tetapi kita tidak pernah bisa memastikan.