Примеры, в которых уникальность решения облегчает поиск

37

Класс сложности состоит из тех -проблем, которые могут быть решены недетерминированной машиной Тьюринга за полиномиальное время, которая имеет не более одного приемлемого вычислительного пути. То есть решение, если оно есть, является уникальным в этом смысле. Весьма маловероятно, что все -проблемы находятся в , потому что по теореме Валианта-Вазирани это будет означать коллапс .UPNPUPPNP=RP

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

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

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

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

Андрас Фараго
источник
7
Ваше первое предложение дает правильное определение UP, но остальные ссылки на UP на самом деле должны относиться к PromiseUP (включая Valiant-Vazirani). В любом случае, это очень интересный вопрос. Два примера: 1) Факторинг находится в UP и имеет алгоритм, более быстрый, чем тот, который известен для NP-полных задач (но Факторинг также в coNP и даже в coUP, поэтому не очень ясно, что уникальность лежит в основе быстрого алгоритма здесь). 2 ) Sodoku, как традиционно определено, находится в PromiseUP, но я не знаю ни одного подхода к решению судоку, который бы использовал обещанную уникальность.
Джошуа Грохов
9
Четность числа гамильтоновых путей можно найти за время ( arxiv.org/pdf/1301.7250.pdf ), в то время как наиболее известный алгоритм для решения задачи занимает почти времени. 1.618n2n
Алексей Головнев
8
Вот пример из квантовых вычислений: рассмотрим задачу поиска по n элементам. Если вы знаете, что существует ровно 1 помеченный элемент, вы можете найти его с помощью точного квантового алгоритма с запросами . Если вы не знаете количество помеченных элементов, любой точный квантовый алгоритм требует запросов. Θ(n)n
Робин Котари

Ответы:

22

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

Алгоритм Хертли основан на важном алгоритме PPSZ Патури , Пудлака, Сакса и Зейна для -SAT, который, я считаю, все еще является самым быстрым для (см. Также эту статью энциклопедии). Исходный анализ показал лучшие оценки для Unique -SAT, чем для общего -SAT, когда ; впоследствии, однако, Хертли показал в другой статье, что вы можете получить те же оценки для (слегка подправленного) алгоритма PPSZ, не предполагая уникальности. Так что, может быть, уникальность помогает, и это может определенно упростить анализ некоторых алгоритмов, но наше понимание роли уникальности дляkk5kkk=3,4k-SAT все еще растет.

Существуют доказательства того, что Unique -SAT не намного проще, чем обычный -SAT. Гипотеза сильного экспоненциального времени (SETH) утверждает, что , так что переменная -SAT разрешима за времени для каждой константы . В статье Калабро, Импальяццо, Кабанца и Патури было показано , что если выполняется SETH, то то же самое утверждение верно для Unique -SAT. Кроме того, если для общего SAT требуется экспоненциальное время, то есть существует некоторое такое, что общееk δ < 1 n k O ( 2 δ n ) k 3 k k k 3 , ϵ > 0 k O ( 2 ϵ n )kkδ<1nkO(2δn)k3kkk3,ϵ>0k-SAT не может быть решен за время , тогда то же самое должно быть верно для Unique 3-SAT. Смотрите статью для наиболее общего утверждения. O(2ϵn)

(Примечание: запись подавляет полиномиальные множители во входной длине.)O

Энди Друкер
источник
1
"true для уникального 3-SAT" "true для уникального k-SAT"
Привет, Рики, я не вижу проблем с написанным. Последнее утверждение об уникальном 3-SAT содержится в реферате статьи.
Энди Друкер
Ах, я вижу, что для того, что я говорил, нужно было использовать разные s, что могло бы привести к путанице. k
16

Проблема кратчайших 2-вершинных непересекающихся путей в неориентированных графах, недавно решенная (ICALP14) А. Бьорклундом и Т. Хусфельдтом. Но детерминированное решение для случая существования единственного решения. В случае, когда существует более одного решения, они показали, что проблема принадлежит RP . Как упоминали авторы статьи, неизвестно, находится ли проблема в P в общем сценарии.

Saeed
источник
3
Спасибо, это очень интересно. Общий случай, когда решение не является уникальным, также является хорошим примером естественной (или даже практической) задачи о графе, которая в настоящее время доказана в RP, но неизвестна в P.
Андрас Фараго
10

Вне теории сложности и анализа алгоритмов предположение о том, что может быть только одно решение, формирует основу для некоторых стандартных правил, используемых для вывода решения в головоломках Судоку. Эти правила обычно включают в себя поиск путей, с помощью которых части головоломки могут иметь два или более решений, которые не взаимодействуют с остальной частью головоломки. Этого не может быть в реальном решении, поэтому, если шаблон, который угрожает вызвать это, найден, то он должен быть нарушен, что позволяет решающему устройству вывести ограничения на то, как может выглядеть фактическое решение. См. Http://www.brainbashers.com/sudokuuniquerectangles.asp, где приведены некоторые примеры правил вывода, основанных на уникальности.

Дэвид Эппштейн
источник
9

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

Предположение об единственности означает, что соотношение числа Хэма. путь - это то же самое, что решить, является ли граф гамильтоновым.

Метод Бьёрклунда детерминистически вычисляет четность числа гамильтоновых циклов в то время как самый известный рандомизированный алгоритм для неориентированной гамильтоничности работает в , а лучший детерминированный алгоритм для направленной гамильтоничности (до насколько мне известно), это все еще 50-летний алгоритм динамического программирования Беллмана, Хелда и Карпа.O ( 1,665 n ) O ( n 2 2 n )O(1.619n)O(1.657n)O(n22n)

RB
источник