Проблемы в

27

Какие проблемы, как известно, принадлежат но не известны как принадлежащие P ?BPPP

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

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

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

Bruno
источник
6
Ответы на этот пост содержат два примера cstheory.stackexchange.com/questions/11425/…
Мохаммад Аль-Туркистани

Ответы:

13

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

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

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

Найти простое число в интервале [N,N+log17N]

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

Питер Шор
источник
Если быть точным, какую версию решения этих проблем вы имеете в виду? Спасибо.
Усул
@usul: Я не имею в виду решение этих проблем. Нужно ли мне? Я понимаю, что технически BPP состоит только из проблем решения. В большинстве случаев проблемы с решением и функциональные проблемы более или менее эквивалентны, что означает, что вы можете рассматривать только проблемы с решением без потери общности. Я не уверен, что это верно для этого вопроса, и я не знаю, заботится ли ОП только о проблемах с решением или нет.
Питер Шор
n[N,5N/4]
[N,5N/4]N>106N106
a,b[a,b]
10

(2)

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

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

|K|=O(logn)|K|

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

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

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

(Ryes,Rno)RRyesR({0,1}×{0,1})RnoRΠ(Ryes,Rno)Π(Ryes,Rno)

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

c>7/12N[N,N+Nc]

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

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