Проблемы в

Какие проблемы, как известно, принадлежат но не известны как принадлежащие ? $\mathsf{BPP}$ $\mathsf P$

Точнее, меня интересуют независимые проблемы, то есть чьи дерандомизации, как известно, не эквивалентны. Например, известно, что дерандомизация PIT и многомерная полиномиальная факторизация эквивалентны, и я бы посчитал их только одной проблемой.

Мотивация моего вопроса состоит в том, что обычно говорят, что «в мало проблем, о которых известно, что они не находятся в » $\mathsf{BPP}$ $\mathsf{P}$ , но я не смог найти их список. В частности, если мне приходится цитировать задачи в этой категории, я обычно цитирую факторизацию одномерных многочленов над конечными полями или факторизацию многомерных многочленов. Я предполагаю, что существуют примеры, которые не связаны с полиномиальной факторизацией, например, в других областях, таких как теория графов или теория формальных языков.

PS: я нахожу любопытным, что подобный вопрос еще не существует на этом сайте. Мои извинения, если я просто не нашел его (или их)!

derandomization Bruno
источник

Ответы на этот пост содержат два примера cstheory.stackexchange.com/questions/11425/…

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

Ответы:

Если вы спрашиваете о независимых проблемах, как насчет:

Найти простое число в интервале , Найти два простых числа, произведение которых находится в интервале , Найти три простых числа, произведение которых находится в интервале , Найти четыре простых чисел, произведение которых находится в интервале , Найти пять простых чисел, произведение которых находится в интервале $[N, 5N/4]$
$[N, 9N/8]$
$[N, 17N/16]$
$[N, 33N/32]$
, . $[N, 65N/64]$
$\ldots$

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

Найти простое число в интервале $[N, N+\log^{17} N ]$

решает все это.

Питер Шор
источник

Если быть точным, какую версию решения этих проблем вы имеете в виду? Спасибо.

Усул

@usul: Я не имею в виду решение этих проблем. Нужно ли мне? Я понимаю, что технически BPP состоит только из проблем решения. В большинстве случаев проблемы с решением и функциональные проблемы более или менее эквивалентны, что означает, что вы можете рассматривать только проблемы с решением без потери общности. Я не уверен, что это верно для этого вопроса, и я не знаю, заботится ли ОП только о проблемах с решением или нет.

Питер Шор

n

$n$

[N, 5 N / 4]

$[N,5N/4]$

[N, 5 N / 4]

$[N, 5N/4]$

N > 10^{6}

$N > 10^6$

N \leq 10^{6}

$N \leq 10^6$

a, b

$a,b$

[a, b]

$[a,b]$

$(2^\ell)$

Тем не менее, я могу думать только о двух случаях, когда это использование приведет к разнице между BPP и P.

Первый - недавний алгоритм для двух кратчайших непересекающихся путей ( авторский PDF ), Björklund и Husfeldt, ICALP 2014.

$|K|=O(\log n)$ $|K|$

Магнус Вальстрём
источник

Я не специалист, но , возможно , некоторые (не так естественно?) Примеры могут быть получены непосредственно с использованием техники детерминировано снижения BPP проблемы поиска в задачах принятия BPP , представленных в:

Одед Голдрайх, В Мире П = БПП. Исследования по сложности и криптографии 2011: 191-232

$(R_{yes},R_{no})$ $R$ $R_{yes} \subseteq R \subseteq (\{0, 1\}^∗ \times \{0, 1\}^∗) \setminus R_{no}$ $R$ $\Pi$ $(R_{yes},R_{no})$ $\Pi$ $(R_{yes},R_{no})$

Теорема может быть распространена на общие задачи построения, например (см. Следствие 3.9 ) рассмотреть задачу нахождения простого числа на достаточно большом интервале:

$c > 7/12$ $N$ $[N, N + N^c]$

Рандомизированный алгоритм выполняется за ожидаемое полиномиальное время; детерминированный полиномиальный алгоритм времени не известен; но если BPP = P, то такой детерминированный полиномиальный алгоритм времени должен существовать (потому что его можно свести к решению BPP-решения).

Марцио де Биаси
источник