Какой класс сложности наиболее тесно связан с тем, что человеческий разум может быстро выполнить?

Этот вопрос я задавался вопросом некоторое время.

Когда люди описывают проблему P против NP, они часто сравнивают класс NP с творчеством. Они отмечают, что составление симфонии качества Моцарта (аналог задачи NP) кажется намного сложнее, чем проверка того, что уже составленная симфония имеет качество Моцарта (аналог задачи P).

Но действительно ли NP - это «класс творчества»? Разве не много других кандидатов? Есть старая поговорка: «Стихотворение никогда не заканчивается, только заброшено». Я не поэт, но для меня это напоминает идею чего-то, для чего нет определенного правильного ответа, который можно проверить быстро ... это напоминает мне больше о coNP и проблемах, таких как TAUTOLOGY, чем NP или SAT. Я предполагаю, что я имею в виду, что легко проверить, когда стихотворение «неправильно» и нуждается в улучшении, но трудно проверить, когда стихотворение «правильно» или «закончено».

Действительно, NP напоминает мне больше о логике и мышлении левого мозга, чем о творчестве. Доказательства, инженерные проблемы, головоломки Судоку и другие стереотипно «проблемы с левым полушарием» - больше NP и их легко проверить с точки зрения качества, чем поэзию или музыку.

Итак, мой вопрос: какой класс сложности наиболее точно отражает совокупность того, что люди могут достичь своим разумом? Я всегда безучастно удивлялся (и без каких-либо научных доказательств, подтверждающих мои предположения), возможно, левое полушарие не является приблизительным SAT-решателем, а правое полушарие мозга не является приблизительным TAUTOLOGY-решателем. Возможно, разум настроен на решение проблем PH ... или, возможно, он может даже решить проблемы PSPACE.

Я предложил свои мысли выше; Мне любопытно, может ли кто-нибудь предложить лучшее понимание этого. Чтобы сформулировать мой вопрос кратко: я спрашиваю, какой класс сложности должен быть связан с тем, что может достигнуть человеческий разум, и для доказательства или аргумента, подтверждающего вашу точку зрения. Или, если мой вопрос некорректен и не имеет смысла сравнивать людей и классы сложности, почему это так?

Благодарю.

Обновление : я оставил все, кроме заголовка без изменений, но вот вопрос, который я действительно хотел задать: какой класс сложности связан с тем, что человеческий разум может выполнить быстро ? Что такое «полиномиальное человеческое время», если хотите? Очевидно, что человек может моделировать машину Тьюринга, учитывая бесконечное время и ресурсы.

Я подозреваю, что ответ - либо PH, либо PSPACE, но я не могу сформулировать разумный, последовательный аргумент, почему это так.

Также обратите внимание: меня интересует, что люди могут приближать или «делать большую часть времени». Очевидно, что ни один человек не может решить сложные случаи SAT. Если разум является приблизительным X- решателем, и X завершен для класса C , это важно.

Я не утверждаю, что это полный ответ, но вот некоторые мысли, которые, надеюсь, соответствуют тому, что вы ищете.

$n \to \infty$

Люди, как правило, хорошо справляются с конечными случаями NP-завершенных головоломок, и все же находят их достаточно нетривиальными, чтобы развлекать. Конечные экземпляры PSPACE-завершенных игр, в которые мы играем, считаются одними из наиболее сложных интеллектуальных задач этого типа. Это, по крайней мере, говорит о том, что PSPACE «достигает верхних пределов» наших способностей. (Тем не менее, наши оппоненты в этих играх с полным PSPACE, как правило, другие люди. Даже когда оппоненты являются компьютерами, компьютеры не являются идеальными оппонентами. Это приводит к вопросу о силе интерактивных доказательств, когда игроки ограничены в вычислительном отношении. также техническая особенность, заключающаяся в том, что некоторые обобщения этих игр являются EXP-полными, а не PSPACE-полными.)

В некоторой степени размеры проблем, возникающие в реальных головоломках / играх, были отрегулированы в соответствии с нашими возможностями. Судоку 4х4 было бы слишком легко, а значит скучно. 16x16 Судоку заняло бы слишком много времени (не больше, чем время жизни вселенной, но больше, чем люди обычно готовы сидеть, чтобы решить головоломку Судоку). 9x9 кажется размером "Златовласка" для людей, решающих судоку. Точно так же, играть в «Свободную ячейку» с колодой из 4 мастей по 13 карт в каждой и 4 свободных ячеек, кажется, примерно та сложность, которую можно решить, но в то же время сложная для большинства людей. (С другой стороны, одна из самых умных людей, которых я знаю, способна решать игры Free Cell, как если бы она просто считала натуральные числа «1,2,3,4, ...»). Аналогично для размеров Го и Шахмат. доски.

Вы когда-нибудь пытались вычислить перманент 6x6 вручную?

$< 10^{10}$

И наоборот, для проблем в EXP любой размер проблемы ниже «пятой экспоненты» имеет шанс быть решаемым большинством людей в разумные промежутки времени.

Что касается остальной части PH, то в естественных играх, в которые люди играют с фиксированным количеством раундов, не так много. Это также как-то связано с тем фактом, что мы не знаем о многих естественных проблемах, завершенных для уровней PH выше третьего.

Как упомянул Серж, FPT играет здесь свою роль, но (я думаю) главным образом в том, что с некоторыми проблемами, естественно, связано более одного «размера ввода».

Тезис « Обучаемое познание» постулирует, что когнитивные способности человека ограничены вычислительной способностью к обучению. Таким образом, тезис P-Cognition использует детерминированное полиномиальное время в качестве модели вычислительной управляемости, в то время как в статье ниже утверждается, что тезис FPT-Cognition более уместен. См. Статью Айрис ван Роидж в выпуске журнала «Параметризованная сложность» за июнь 2009 года для более подробного обсуждения и ссылок на другие статьи.

• Ирис ван Рой. Тезис "Обучаемое познание" . Когнитивная наука, 32, с. 939-984, 2008.
• Ирис ван Рой. Параметры, которые делают свет когнитивной работы. FPT News: Параметризованная Сложность Newsletter, июнь 2009 .

Я думаю, что кто-то ведет к неправильной модели, пытаясь экстраполировать те вещи, которые человеческий мозг вычисляет, и я думаю, что было бы лучше принять противоположную точку зрения и вместо этого экстраполировать ее на вычислительную модель.

$TC^0$

Кроме того, я не согласен с утверждением в вопросе о том, что человеческий разум может моделировать машину Тьюринга. Скорее, он может симулировать конечное управление машиной Тьюринга. Для выполнения очень сложных задач кажется необходимым иметь возможность записывать информацию на «ленту».

Классы сложности определяются в терминах асимптотической сложности, следовательно, они плохо сопоставляются с когнитивными способностями людей, которые обязательно ограничены ограниченным размером проблемы.

Основное правило таково: если что-то легко для компьютера, тогда это может быть трудно для человека, и наоборот, если это трудно для компьютера, это может быть легко для человека.

Здесь «легкий / трудный для компьютера» относится к практической обучаемости, а не к абстрактному классу сложности.

Например, сложение списка из 1 миллиарда целых чисел является простым для современного компьютера и трудным для человека, в то время как составление словесного описания изображения легко для человека, но трудно (в настоящее время невозможно в общем случае) для компьютера.

Исследования в области искусственного интеллекта показали, что многие когнитивные задачи, которые люди и животные легко выполняют, в некоторых случаях даже подсознательно, могут быть смоделированы как NP-сложные проблемы. Люди не могут найти оптимальные решения этих проблем для всех размеров, но они могут найти эвристические решения для практических размеров гораздо лучше, чем самые известные алгоритмы ИИ.

Также обратите внимание, что различие между левым и правым полушариями, которое вы упоминаете, слишком упрощено и устарело. Латерализация функций мозга гораздо более тонкая и может даже варьироваться от одного человека к другому.

Если мы решим изучать сам человеческий мозг, а не то, как люди используют его для решения проблем, я не верю, что это проблема сложности, а скорее вычислимости. Поскольку каждая ТМ нуждается в переходной функции, человек может имитировать шаги ТМ, поэтому человеческий мозг полон по Тьюрингу.

В обратном направлении, могут ли ТМ вычислять все, что делают люди? Краткий ответ: мы не знаем. Предполагая, что тезис Черча-Тьюринга верен, изменится ли ответ или нет, зависит от вашего взгляда на мир (философский, духовный, религиозный и другие). В этом случае мы можем с уверенностью сказать, что человеческий мозг, являющийся частью материального мира, может моделироваться машиной Тьюринга. Остальное до споров и, по крайней мере, на мой взгляд, не имеет отношения к TCS.

$P \neq NP$$NP-P$$10^{10^{100}}n$$n$$2 \log 10^{10^{100}}$раз больше информации на каждом шаге алгоритма ускорения. Конечно, определенная нижняя граница была бы необходима, чтобы гарантировать, что более быстрый алгоритм (включая константы) не существует.

Итак, если вы хотите точно рассчитать, с какими проблемами человеческий мозг, учитывая ограничения реальной жизни, такие как отвлекающие факторы, объем внимания и т. Д., Вы должны иметь верхнюю границу количества выполненных шагов, верхнюю границу количество последовательных шагов (даже самый преданный исследователь должен спать и есть), ограничение пространства (не только в ленте, но и в любых «внутренних» регистрах), моделирование того, как действует память, потому что в отличие от ТМ, мы может забыть что-то, что мы пишем в нашей «рабочей ленте», или точное состояние, и, конечно же, определить соотношение между временами машины и временем в секундах или «шагами человеческого мозга». Возможно, другие проблемы будут всплывать как вы. По иронии судьбы, возможно, одна или несколько из этих проблем не могут быть решены человеческим мозгом, по крайней мере, эффективно.

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

Если вы дадите человеку карандаш и бумагу, она сможет решить практически любую проблему, действуя как машина. Так что я думаю, что это не главное.

Имхо, что делает человеческое мышление абстракцией, то есть люди не управляют вещами (в первую очередь), они создают взгляды на вещи. Хотя, как я должен признать, я не могу предоставить почти готовую теорию для абстракции.

| =

Я долго думал над этим вопросом. Вот к чему я пришел:

мы, люди, думаем обычно в абстрактных ментальных объектах, а не в алгоритмах. Числа, которые мы знаем, язык, на котором мы говорим, мышление было некогда абстрактной идеей. Эти идеи были расширены философами, учеными и затем использованы. То, что мы имеем, отличается от того, как они возникли.

Ваш вопрос - «Какой класс сложности наиболее точно отражает всю совокупность достижений людей в их умах?» можно ответить, только если имеется достаточно доказательств того, что люди следуют математическим / алгоритмическим / вероятностным моделям. Ну, они могут следовать каждому из вышеперечисленного или их комбинации. Но они на самом деле что-то другое. Это просто нормальное человеческое мышление. Расщепление творческих мыслей, таких как сочинение Моцарта, поэма или мышление спортсмена соответствующими формальными способами (математические / логические методы их мышления) и попытка обобщения, было бы настоящим подвигом, хотя и не уверен, что это будет возможно.

Я также думаю, что мы могли бы приблизить класс сложности, но мы никогда не можем быть уверены.