Задачи, NP-полные при рандомизированном или P / poly сокращении.

В этом вопросе мы, кажется, идентифицировали естественную проблему, которая является NP-полной при рандомизированных сокращениях, но, возможно, не при детерминированных сокращениях (хотя это зависит от того, какие недоказанные предположения в теории чисел верны). Известны ли еще такие проблемы? Существуют ли какие-либо естественные проблемы, которые являются NP-полными при сокращениях P / poly, но неизвестно, что они находятся при сокращениях P?

cc.complexity-theory np-hardness big-list randomness reductions Питер Шор
источник

Уникальный SAT - это

-hard при рандомизированном сокращении.

N P

$NP$

Мохаммед Аль-Туркистани

Я не понимаю, почему Unique SAT не должен считаться ответом (хотя это было не совсем то, что я искал). Я думаю, что это считается естественной проблемой.

Питер Шор

Я просто хотел добавить, что самой короткой векторной проблемой для LLL при норме

для рандомизированных сокращений (статья Ajtai здесь ) является NP-Hard. Насколько я знаю, он не известен как NP-Hard при неслучайных сокращениях, поэтому он не соответствует вашим критериям, но я подумал, что в любом случае об этом следует упомянуть.

L_{2}

$L_2$

user834

@Joshua: В некоторых NP-полных задачах, связанных с головоломками (таких как судоку), уникальность решения является естественным предположением. Я предполагаю, что это делает SAT с не более чем одним решением (я предпочитаю называть его однозначным SAT) более естественным, чем это может показаться на первый взгляд.

Цуёси Ито

Почему все пишут ответы в комментариях? : P

Сянь-Чжи Чан 之之

Ответы:

При рандомизированном уменьшении с вероятностью (известная также как сводимость, о обсуждении рандомизированных сокращений см. «Об уникальной удовлетворяемости и рандомизированных сокращениях») $\frac{1}{2}$ $\gamma$

Линейная делимость
Двоичные квадратичные диофантовы уравнения

являются NP-полными, но то же самое не известно для детерминированных сокращений (насколько я знаю, для слегка устаревшего обсуждения этой ситуации см. здесь ). сводимость была введена Леонардом Адлеманом и Кеннетом Мандерсом в статье « Приводимость, случайность и интрацибельность » (там же были предложены доказательства вышеупомянутых проблем). $\gamma$

Есть и другие подобные примеры в « Каталоге классов сложности », но я не проверял, что известно об их NP-полноте при детерминированных сокращениях.

Александр бондаренко
источник

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

Валиант-Вазирани теорема утверждает , что если СБ Уникальный , то . Чтобы доказать свою теорему, они показали, что задача обещания Unique SAT равна $\in P$ $NP=RP$ -твердой при рандомизированных редукциях. $NP$

[1] Доблестный, Лесли; Вазирани, Виджай. «NP столь же прост, как обнаружение уникальных решений», Теоретическая информатика, 47: 85–93

Мухаммед Аль-Туркистани
источник

По предложению Питера я преобразовал свой комментарий в ответ:

$L_2$ $NP$

user834
источник