Являются ли

66

В настоящее время решается либо полная проблема, либоP S P A C ENппSпAСЕ complete в общем случае невозможно для больших входов. Однако оба они разрешимы в экспоненциальном времени и в полиномиальном пространстве.

Поскольку мы не можем создавать недетерминированные или «счастливые» компьютеры, имеет ли это какое-то значение для нас, если проблема является -полной или P S P A C E -полной?NппSпAСЕ

Алекс тен Бринк
источник

Ответы:

82

Это очень хороший вопрос, о котором я много думал: влияет ли тот факт, что проблема является -полной или P S P A C E -полной, на самом деле сложность проблемы в наихудшем случае во времени? NпPSPAСЕБолее размыто, действительно ли такое различие влияет на сложность проблемы «типичного случая» на практике?

Интуиция говорит , что -полной проблема сложнее , чем N P -полных один, независимо от того, какой степени сложности вы используете. Но ситуация тонкая. Это может быть, например, то, что Q B F (количественные булевы формулы, каноническая P S P A C E -полная задача) находится в субэкспоненциальном времени тогда и только тогда, когда S A T (Удовлетворенность, каноническая N PпSпAСЕNпQВFпSпAСЕSATNппроблема в субэкспоненциальном времени. (Одно направление очевидно; другое направление будет основным результатом!) Если это так, то, возможно, с точки зрения «Я просто хочу решить эту проблему», не имеет большого значения, является ли проблема -комплект или N PпSпAСЕNп -полный: в любом случае, субэкспоненциальным алгоритм одного подразумевает субэкспоненциальный алгоритм для других.

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

Пусть - булева формула для n переменных, где n - четное. Предположим, у вас есть выбор между двумя формулами, которые вы хотите решить:F(Икс1,...,ИксN)NN

.Φ1знак равно(Икс1)(Икс2)(ИксN-1)(ИксN)F(Икс1,...,ИксN)

Φ2знак равно(Икс1)(Икс2)(ИксN-1(ИксN)F(Икс1,...,ИксN)

(То есть в Φ2 , квантификаторов чередуются.)

Как вы думаете, какой из них легче решить? Формулы типа или формулы типа Φ 2Φ1Φ2 ?

Можно было бы подумать , что очевидный выбор , как это только Н Р -полное , чтобы решить его, тогда как Ф 2 является Р С Р С Й -полной проблемой. Но на самом деле, по нашим наиболее известным алгоритмам, Φ 2 является более простой задачей. Мы не знаем, как решить Φ 1 для общего F менее чем за 2 n шагов. (Если бы мы могли сделать это, у нас были бы новые нижние границы размера формулы!) Но Φ 2 может быть легко решена для любого F в рандомизированном OΦ1NпΦ2пSпAСЕΦ2Φ1F2NΦ2F время, используя рандомизированный поиск по дереву игр! Для справки см. Главу 2, раздел 2.1, в Мотвани и Рагхаване.О(20,793N)

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

Райан Уильямс
источник
16
Хороший ответ и интересный дубль.
Суреш Венкат
Мне приходит в голову, что вышесказанное является довольно хорошим примером того, что мы подразумеваем под «мелкозернистой сложностью» (программа осени 2015 года в Институте Саймонса). Одна из ключевых идей заключается в том, что теория сложности может выглядеть совсем иначе, когда вместо того, чтобы пытаться найти для каждой проблемы (потенциально причудливую) вычислительную модель, для которой эта проблема является «полной», нужно просто сосредоточиться на понимании того, что является наилучшим возможным временем выполнения. показатель для проблемы.
Райан Уильямс
37

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

Для задач решения - задач, на которые у каждого экземпляра есть ответ « ДА » или « НЕТ » - NP - это именно тот класс задач, для которого мы можем эффективно проверить предполагаемое доказательство того, что данный экземпляр является экземпляром « ДА », детерминистически, если мы представлены с одним. Например, если у вас есть удовлетворительное назначение переменных для экземпляра 3-SAT, это назначение позволяет вам эффективно доказать, что экземпляр выполним. Такое удовлетворительное задание может быть трудно найти, но если оно у вас есть, вы можете легко доказать другим, что этот экземпляр выполним, просто убедив их проверить решение, которое вы нашли.

Аналогично, для coNP существуют эффективно проверяемые доказательства для случаев « НЕТ »; и для проблем в NP  ∩  coNP , вы можете сделать оба. Но для PSPACE- неполных задач таких процедур не существует - если только вы не можете доказать довольно впечатляющие равенства классов сложности.

Ниль де Бодрап
источник
Я думаю, что речь идет об «оптимизационной» версии NP-complete и PSPACE-complete задач. Например, есть ли разница (с точки зрения сложности) между поиском решения для SAT и для QBF? И вообще, есть ли характеристика проблем оптимизации, какая версия решения является NP-полной или PSPACE-полной?
Ламин
@Lamine: я не вижу различия, которое вы делаете в вопросе (по крайней мере, между простым решением и полной оптимизацией). Возможно, вы имеете в виду, что спрашивающего интересует только вопрос о ресурсах, необходимых для того, чтобы найти этот ответ, и он не интересуется другими мерами сложности проблемы, и в этом случае я согласен, что мой ответ не отвечает на этот вопрос. В любом случае, выше мой ответ на вопрос в его нынешнем виде.
Ниль де Бёдрап,
5
Очень хороший ответ.
Дэйв Кларк,
Возможность эффективной проверки не помогает при вычислении решения (если только P = NP). NP и co-NP позволяют атаковать проблему путем угадывания и проверки. Этот подход прост в реализации и даже может быть более эффективным, но в худшем случае он не помогает.
Андрас Саламон
@ András: правда - поэтому мой акцент на том, что поиск решений - не единственная важная вещь в предисловии к моему ответу.
Ниль де Боудрап
36

Мы не знаем, как построить сложные проблемы в среднем случае из (наихудшего) NP-полных задач, но мы можем сделать это для PSPACE (см. Köbler & Schuler (1998) ), чтобы создать проблемы даже для равномерного распределения, которое не может быть решается на большинстве входов, если не все PSPACE легко вычислить.

Лэнс Фортноу
источник
20

С практической стороны важно помнить, что NP-полнота не является барьером для многих проблем на практике. Сдвоенные инструменты решателей SAT и CPLEX (для целочисленного линейного программирования) достаточно мощны и достаточно хорошо спроектированы, чтобы часто можно было решать большие случаи проблем с NP-завершением, либо обрамляя проблему как подходящий ILP, либо сокращая до SAT.

Я не знаю о так же хорошо спроектированных решениях для проблем в PSPACE.

Суреш Венкат
источник
11
Существует ежегодно конкурс предназначен для повышения QBF решателей . Я не использовал их много.
Раду GRIGore
7

Вы можете подумать об этом следующим образом: есть ли у математической задачи доказательство, которое может быть прочитано человеком, или оно по сути требует «компьютерного доказательства». Примеры: является ли начальная позиция шашек ничьей? (Ответ: да.) Является ли стартовая позиция в шахматах победой белых? (Ответ: неизвестно, но большинство гроссмейстеров считают, что это ничья.)

Доказательство того, что начальная позиция шашек является ничьей, в конечном итоге требует признания того, что компьютер действительно точно проверял множество особых случаев. Если доказательства о шахматах когда-либо существуют, то, вероятно, потребуется, чтобы читатели смирились с тем, что компьютер правильно проверял даже более особые случаи. И вполне может быть, что нет более короткого способа доказательства этих утверждений. Это проблемы в PSPACE. Если в NP проблема "праведна", то (интуитивно) человек может держать все доказательства в своей голове. Этот человек, возможно, должен быть очень специализированным математиком, конечно.

N1000000

Аарон Стерлинг
источник
Можно ли также утверждать, что у неполных с coNP проблем есть эта проблема (иногда) требующая «компьютерного доказательства»?
Филип Уайт
@ Филип Уайт: Я не думаю, что это то же самое. Скажи "шахматная ничья" в КНП. Чтобы сказать «нет», все, что мне нужно сделать, это продемонстрировать единственную линию принуждения, которую легко проверить. Тем не менее, мы ожидаем, что, даже если такая линия существует, вероятно, будет очень трудно доказать, что она действительно «форсирует». Таким образом, проблема не дает гарантии простоты, если она разрешима в определенном направлении. «Шахматы - ничья», вероятно, по своей природе требует, чтобы компьютер доказал, является ли это правдой или ложью.
Аарон Стерлинг
5

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

Разница между доказательством и проверкой также обнаруживается. Некоторые решатели SAT (такие как MiniSAT 1.14 и множество других) предоставляют доказательства. Создание доказательств в современных решателях QBF нетривиально. (Следующее утверждение взято из слухов) В соревновании QBF есть большие случаи, когда решатели, очевидно, дают разные результаты. В отсутствие корректирующих решателей мы не знаем, какой результат является правильным.

Виджай Д
источник
0

Если вы посмотрите на практические результаты по SAT и шахматам, то есть разница - проблемы с NP-полнее поддаются решению, чем задачи с PSPACE. SAT решатели сегодня могут обрабатывать более тысячи переменных, но лучший шахматный движок, в то же время, может рассчитывать только до 20 ходов.

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

С чередованием кванторов, да, есть умные методы сокращения, но все же структура не так богата, как в формуле CNF.

Позвольте мне предсказать будущее. SAT-решение превратится в P, изучив формулу и по существу избегая поиска, в то время как шахматы дойдут до P, воспользовавшись поиском в дереве игры.

Зируй Ван
источник