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

59

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

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

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

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

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

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

Благодарю.

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

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

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

Филип Уайт
источник
18
+1 за указание на то, что удивительно много реальных дизайнерских задач имеют некоторый вкус coNP. Это относится и к технике. Если машина ломается или разрушается мост, это легко проверяемое доказательство того, что проект был плохим, но как доказать, что проект хорош ...?
Юкка Суомела
4
Мозги являются физическими устройствами, и, следовательно, конечны. Класс сложности, который вы ищете, является некоторым подходящим подмножеством SPACE (O (1)) = TIME (O (1)).
Джеффс
15
@JeffE: Компьютеры также являются физическими устройствами, и, следовательно, конечно. Тем не менее, мы все еще думаем, что классы сложности помогают нам понимать компьютеры (хотя не однозначно, а именно, много дискуссий о том, «что если P = NP, но показатель степени или константы огромны»). С другой стороны, мощность отдельного компьютера увеличивается в гораздо более быстром масштабе времени, чем мощность отдельного мозга ...
Джошуа Грохов
4
Я думаю, что это была Пунья Бисвал, которая придумала эту шутку: причина, по которой нам трудно придумать явные сложные функции, заключается в том, что наш мозг не достаточно силен, чтобы представить такие функции :)
arnab
3
Джошуа: Теоретические компьютерные ученые не изучают компьютеры; мы изучаем математические абстракции компьютеров. Дайте мне математическую абстракцию человеческого мозга, и вы, вероятно, ответите на свой вопрос.
Джефф

Ответы:

17

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

n

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

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

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

<1010

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

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

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

Джошуа Грохов
источник
13

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

Серж Гасперс
источник
Есть ли доказательства того, что это правда?
yters
13

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

TC0

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

Кристоффер Арнсфельт Хансен
источник
2
Что касается моделирования человеком ТМ ... Я предполагал, что людям разрешены разумные ресурсы, такие как карандаш и бумага. Ваша точка зрения справедлива, хотя.
Филипп Уайт
3
TC0TC0AC0
4
Записывание фактов, без сомнения, является одной из основных причин, по которой мы прогрессировали как люди, и, возможно, это также привело к развитию нашего мозга. По крайней мере, это позволяет нам создать основу, на которой мы можем строить свои идеи (например, представьте, если TCS или любая другая область основана только на речи). Исходя из этого, я считаю, что если вы удалите человеческие способности «карандашом и бумагой», вы можете также удалить ленту с ТМ и превратить ее в простую конечную машину.
Chazisop
2
AC0
2
Честная оценка. Я полагаю, что если бы NEXP можно было вычислить из таких «простых» схем, это было бы довольно убедительным доказательством того, что мозг, состоящий из «просто» нейронов, действительно мог бы быть достаточно мощным, что согласуется с нашим опытом. OTOH, я думаю, что схема мозга имеет глубину намного выше, чем 3 :).
Джошуа Грохов
10

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

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

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

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

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

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

Антонио Валерио Мицели-Бароне
источник
1
+1 за первый абзац, -1 за все остальное. МНОГИЕ задачи легки как для людей, так и для компьютеров, и МНОГИЕ другие задачи трудны для обоих.
Джеффс
1
Я подумал, что было очевидно, что существуют тривиальные задачи, которые легко выполняются как людьми, так и компьютерами. В любом случае, я обновляю свой ответ, чтобы сделать его более четким.
Антонио Валерио Мицели-Бароне
2

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

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

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

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

chazisop
источник
Предполагая, что у человека конечная память, он не является полным по Тьюрингу. Самое большее, он может моделировать произвольные конечные автоматы, вплоть до некоторого размера. Бессмертный человек с бесконечной бумагой, карандашами и терпением был бы завершен по Тьюрингу.
Антонио Валерио Мицели-Бароне
@ user1749, да, на самом деле это идея. Если вы хотите увидеть человеческий мозг таким, какой он есть, а не потому, что он связан с человеком. Компьютеры завершаются, но их жизнь намного меньше, чем у любого человека. Я уверен, что физическая ТМ не будет длиться тысячелетиями.
chazisop
2

ThC0PNC#P

Бен Стандевен
источник
-1

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

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

| =

modelpractice
источник
-1

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

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

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

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

spiralarchitect
источник