Существуют ли NP-полные проблемы с полиномиальными решениями ожидаемого времени?

24

Существуют ли какие-либо NP-полные задачи, для которых известен алгоритм, согласно которому ожидаемое время выполнения является полиномиальным (для некоторого разумного распределения по экземплярам)?

Если нет, то существуют ли проблемы, для которых было установлено существование такого алгоритма?

Или существование такого алгоритма подразумевает существование детерминированного полиномиального алгоритма времени?

cc.complexity-theory np-hardness Стив Крун
источник

6

Я не совсем понимаю, в чем вопрос. Вы запрашиваете средние результаты для NP-сложных задач или же вы можете решить, можем ли мы решить NP-сложные задачи в худшем случае в ожидаемое полиномиальное время?

Мориц

2

Что вы подразумеваете под "ожидаемым временем работы"? Вы берете ожидание относительно некоторого случайного распределения входных данных (как кажется, думает большинство ответов), или от распределения случайных битов, используемых алгоритмом (обычное значение для рандомизированных алгоритмов), или обоих?

Джефф

@ Мориц: Я спрашиваю о средних результатах для NP-сложных задач. Решение сложных для NP задач в наихудшем случае в ожидаемое полиномиальное время кажется мне еще более сильным результатом, поэтому я бы также заинтересовался такими результатами. @JeffE Я говорю об ожидаемом времени относительно некоторого распределения по экземплярам. Если алгоритм рандомизирован, можно рассчитывать и на случайные биты. Но мой вопрос не в первую очередь о рандомизированном алгоритме.

Стив Кроун

3

Простой метод заполнения дает вам возможность построить их из любой проблемы.

Предположим, что - это полный язык, который требует времени для решения. Тогда пусть будет Тогда решается следующим образом: алгоритм линейного времени проверяет, имеет ли входная строка четное число символов, из которых первые равны . Если нет, он отклоняет; в противном случае это решает $L$ $NP$ $O(2^{n})$ $K$

K = {1^{n} x | ‖ x ‖ = n and x \in L}

$K=\{1^nx\ |\ \|x\|=n \text{ and }x\in L\}$

K

$K$

n

$n$

1^{n}

$1^n$

x \overset{?}{\in} L

$x\overset{?}{\in}L$ , Если

рисуется случайным образом равномерно, ожидаемое время для решения

равно

y \in_{R} {0, 1}^{2 n}

$y\in_R \{0,1\}^{2n}$

y \overset{?}{\in} K

$y\overset{?}{\in}K$

\frac{1}{2^{2 n}} (2^{n} \cdot 2^{n} + (2^{2 n} - 2^{n}) O (n)) = 1 + (1 - \frac{1}{2^{n}}) O (n) \in O (n) .

$\frac{1}{2^{2n}}\big(2^n\cdot 2^n+(2^{2n}-2^n)O(n)\big) = 1+(1-\frac{1}{2^n})O(n)\in O(n).$

является -завершенным. Редукция из : $K$ $NP$ $L$

x \in {0, 1}^{n} \mapsto 1^{n} x

$x\in \{0,1\}^n \mapsto 1^nx$

Лиуве Винхуйзен
источник

13

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

$n$

Ссылка: «Алгоритм нахождения циклов Гамильтона в случайных графах»

Боллобас, Феннер, Фриз

http://portal.acm.org/citation.cfm?id=22145.22193

Аарон Рот
источник

10

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

Известно, что некоторые проблемы решетки имеют такие редукции от худшего к среднему. См., Например, « Создание сложных примеров проблем с решеткой» от Ajtai и обзорную статью от Micciancio.

Ян
источник

9

$n$ $n$

Ссылка:

Александр Д. Скотт и Григорий Б. Соркин. Решение редких случайных случаев Max Cut и Max 2-CSP за линейное ожидаемое время. Гребень. Вероятно. Comput., 15 (1-2): 281-315, 2006. Препринт

Серж Гасперс
источник

2

Θ (n)

$\Theta(n)$

G (n, c / n)

$G(n,c/n)$

@ Барт: Я мог неправильно понять вопрос. Я утверждаю, что Max 2-CSP с линейным числом предложений является NP-сложным, но существует алгоритм с ожидаемым линейным временем, решающий эту проблему для случайных случаев.

Серж Гасперс

По сути, если я правильно понимаю ваш аргумент, вы говорите, что Max 2-CSP, снабженный распределением G (n, c / n) по базовым графам, может быть решен за ожидаемое линейное время. Я согласен с Бартом в том, что распределение не кажется мне полностью «разумным» или «естественным», но я думаю, что оно отвечает на мой вопрос адекватно.

Стив Кроун

@ Стив: Я согласен.

Серж Гасперс

7

Это не дает полного ответа на ваш вопрос, но для просмотра результатов по случайным случаям 3-SAT вы можете увидеть это: www.math.cmu.edu/~adf/research/rand-sat-algs.pdf

Обычно трудно определить, что на самом деле означает «разумное распределение». Вы можете перейти по этой ссылке, чтобы узнать больше об этом в опросе Богданова и Тревизана «Средняя сложность»: http://arxiv.org/abs/cs/0606037 .

Григорий Ярославцев
источник

Спасибо за ссылки. К сожалению, результаты 3-SAT "с высокой вероятностью" недостаточно сильны (насколько я вижу), чтобы подтвердить мой запрос. Я согласен, что "разумное распределение" может быть волосатым. В этом я предпочел бы, чтобы распределение явно не выбиралось так, чтобы «эффективное пространство экземпляров» не просто сводило проблему к той, о которой известно, что она находится в P.

Steve Kroon

5

«Раскраска случайных графов в ожидаемое полиномиальное время» Амин Кожа-Оглан и Ануш Тараз

$G \in G(n, p)$ $p < 1.01/n$ $O(√np)$

http://www.springerlink.com/content/87c17d4dacbrc0ma/

Джоэл Рыбицки
источник

Существуют ли NP-полные проблемы с полиномиальными решениями ожидаемого времени?

Ответы: