В статье Стивена Кука о проблеме P против NP [1] он утверждает следующее [2]:
Тезис осуществимости: естественная задача имеет выполнимый алгоритм, если он имеет алгоритм полиномиального времени.
У меня вопрос, что именно он (или вообще, на самом деле, что один) подразумевает под « естественной проблемой»? Разговоры о естественных проблемах кажутся достаточно распространенными, но мне еще предстоит найти определение. Кажется, я что-то упустил. Вот несколько возможных ответов, о которых я думаю:
Первый возможный ответ
Кук говорит в своей статье, что «естественное» должно быть объяснено. Он говорит: «Как правило, мы не рассматриваем класс с параметром как естественный, такой как набор графов, встраиваемых на поверхности рода k , k > 1». [3] Теперь, во-первых, это, кажется, говорит о том, что » естественный "не то, что он есть; но если каждая проблема является естественной или нет, и это полностью описывает все проблемы, которые не являются естественными, то этого будет достаточно для определения естественной. (Но квалификатор «в целом» предполагает, что это не является достаточным и необходимым описанием проблем, которые не являются естественными.)
Я думаю, что «классы с параметрами» относятся к трактуемости с фиксированными параметрами, под которой мы подразумеваем проблемы, в которых возможные входные данные ограничены, так что выполнимость выполнима. Таким образом, мы можем решить задачу о ранце [4] с помощью алгоритма за полиномиальное время, если зафиксировать вес, который может нести рюкзак (но в общем случае решения за полиномиальное время не существует). Имея это в виду, я понимаю, что быть «естественным» означает, что проблема не ограничена («искусственно» ограничена?) Таким образом, что вытесняет алгоритм с полиномиальным временем из задачи, которая не разрешима за полиномиальное время.
Причина, по которой я не уверен, что это правильный способ понять понятие Кука о «естественном», заключается в том, что я не совсем уверен, что квалификация «естественный» делает здесь. Если вы отбросите «естественный», то получите «проблема имеет выполнимый алгоритм, если он имеет алгоритм полиномиального времени». Но это кажется совершенно разумным: проблема рюкзака не имеет выполнимого алгоритма, потому что она не имеет алгоритма полиномиального времени; у рюкзака с фиксированным параметром-tractability есть выполнимый алгоритм, потому что у него есть алгоритм полиномиального времени. Кажется, что оба счета соответствуют понятию, что является проблемой с выполнимым алгоритмом.
Я полагаю, что это может быть лучшим руководством для понимания того, что означает Кук, потому что Кук фактически оборачивается и определяет это. Я также полагаю, что это понятие естественного отражено в этом вопросе StackExchange. [5}
Но есть и другое.
Второй возможный ответ
Уильям Гасарч в своей статье «Классификация проблем по классам сложности» [6] говорит, что он проведет «буквальное обсуждение того, что является естественной проблемой» [7]. В конце статьи [8] происходит обмен в форме диалога, где один из ораторов говорит:
«Что делает проблему естественной? С одной стороны, я не создавал проблему с единственной целью не быть в P. Так что это не проблема тупой задницы. Затем она поднимается до уровня естественности?»
Таким образом, мне кажется, что Гасарх говорит, что если у нас есть проблема, которая намеренно не построена так, чтобы мы могли сказать, что ее нет в P, то это естественно. Таким образом, с небольшим творческим толкованием кажется, что Гасарх говорит что-то, по крайней мере, совместимое с Кук: с одной стороны, Гасарч говорит, что не построение с единственной целью не быть в Р делает проблему не естественной; с другой стороны, Кук говорит, что проблема естественна, если у нее нет параметров. Но простая последовательность не дает определения.
Третий возможный ответ
В статье в Википедии о «хорошо поставленной проблеме» [9] представлено определение понятия «правильно поставленной проблемы» Жака Адамара, а затем утверждается, что правильно поставленная проблема »может рассматриваться как« естественная »проблема. в том, что есть физические процессы, моделируемые этими проблемами ". Итак, проблема естественна тогда и только тогда, когда она моделирует физический процесс?
Согласно Википедии, квалификация Адамара заключается в том, что (i) решение существует, (ii) решение уникально и (iii) поведение решения непрерывно изменяется с начальными условиями. Похоже, это отличается от двух других определений. Я чувствую, что «естественный» не используется точно так же (особенно если мы согласны с интерпретацией, что проблема естественна тогда и только тогда, когда она моделирует физический процесс), но я хотел включить ее, потому что столкнулся с Это в моем исследовании по этому вопросу, и есть точки соприкосновения.
Итак, мой вопрос: что является естественной проблемой? Являются ли какие-либо из этих ответов или их комбинация правильными? Есть какой-то другой ответ, который я пропускаю? Спасибо.
- «Постановка проблемы», 2006 г., размещена в сети на Clay Matmatics; title: «Проблема P vs NP», http://www.claymath.org/sites/default/files/pvsnp.pdf
- п. 3
- п. 4
- https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem
- Сложнее всего известная естественная проблема в P? Я предполагаю, что естественная проблема следует за этим описанием, но не ограничивает k быть самой большой.
- https://www.cs.umd.edu/~gasarch/papers/classcomp.pdf
- п. 2.
- п. 47-8, раздел 25
- https://en.wikipedia.org/wiki/Well-posed_problem
источник
Ответы:
Чтобы было ясно, это не должно быть формализуемо. Это не теорема, это наблюдение за миром - это нормально, если «естественное» здесь субъективно. По аналогии, если кто-то говорит, что «дифференциация - это механика, а интеграция - это искусство», они не приглашают вас формализовать «механику» и «искусство» и доказывать утверждение, они пытаются представить общую перспективу. Таким образом, вы можете немного скучать по лесу из-за деревьев здесь. [Сноска]
В чем смысл автора
Давайте последуем вашему предложению и отбросим слово «натуральный»:
Ну, это технически неправильно. Из-за теоремы иерархии времени мы можем построить произвольно сложные задачи в P (например, требующие времени). Но эти контрпримерные проблемы очень странные, самоссылочные, например, «останавливается ли данная машина Тьюринга на заданном входе в шагов?»n1000 n1000
Таким образом, автор считает, что тезис все еще довольно точен в отношении проблем, которые мы на самом деле хотим решить в реальном мире, и других проблем, возникающих «естественным образом» в течение жизни, не основанной на теории сложности. Поэтому он думает, давайте назовем эти проблемы «естественными» и пересмотрим тезис о целесообразности.
Что является и не является естественным
Конечно, проблема, которая обычно возникает на практике, будет считаться естественной: кратчайшие пути, сортировка, редактирование расстояния, поиск корней, коммивояжер, рюкзак.
Конечно, проблема, которая придумана и определена специально для доказательства результата сложности и ссылается на конкретный класс, не является естественной. Например, «может ли эта строка быть сгенерирована машиной Тьюринга в k состояниях за n раз».
Некоторые вещи менее ясны, например, линейное программирование, но я бы не стал сильно беспокоиться об этом. Изучите множество алгоритмов и проблем сложности и посмотрите, согласны ли вы с общей идеей или найдете примеры, которые, по вашему мнению, противоречат ей.
(В любом случае, как вы подозреваете, я думаю, что «хорошо поставленная проблема», безусловно, неверна).
[сноска] Я не хочу отговаривать вас от попыток формализовать это, просто думая, что вы должны.
источник
Это примерно сводится к тому, может ли определение проблемы быть круглым:
Искусственная проблема - это проблема, созданная для заполнения критериев класса.
Естественная проблема не полагается на свой метод построения для заполнения критериев класса.
Известно, что конструкция Лэднера является NP-промежуточной при условии, что NPI существует.
источник