Problemas em

Quais problemas são conhecidos por pertencerem a mas não por pertencerem a ? $\mathsf{BPP}$ $\mathsf P$

Mais precisamente, estou interessado em problemas independentes , ou seja, cujas derandomizações não são conhecidas como equivalentes. Por exemplo, sabe-se que o PIT derandomizing e a fatoração polinomial multivariada são equivalentes e eu os consideraria apenas um problema.

A motivação da minha pergunta é que é comum dizer que "existem poucos problemas no não se sabe estar em " $\mathsf{BPP}$ $\mathsf{P}$ , mas não consegui encontrar uma lista deles. Em particular, se eu tiver que citar problemas nesta categoria, geralmente cito a fatoração de polinômios univariados sobre campos finitos ou a fatoração de polinômios multivariados. Suponho que existam exemplos que não estejam relacionados à fatoração polinomial, por exemplo, em outros domínios, como a teoria dos grafos ou a teoria formal da linguagem.

PS: Acho curioso que uma pergunta semelhante ainda não exista neste site. Peço desculpas se eu simplesmente não o encontrei (ou eles)!

derandomization Bruno
fonte

As respostas a esta postagem contêm dois exemplos cstheory.stackexchange.com/questions/11425/…

Mohammad Al-Turkistany

Respostas:

Se você está solicitando problemas independentes, que tal:

Encontre um primo no intervalo , Encontre dois números primos cujo produto esteja no intervalo , Encontre três números primos cujo produto esteja no intervalo , Encontre quatro números primos cujo produto está no intervalo , encontre cinco números primos cujo produto esteja no intervalo , . $[N, 5N/4]$
$[N, 9N/8]$
$[N, 17N/16]$
$[N, 33N/32]$
$[N, 65N/64]$
$\ldots$

É extremamente provável que, se você realmente tivesse um algoritmo polinomial para resolver o primeiro deles, teria um algoritmo polinomial para todos eles. Mas não vejo como reduzir formalmente nenhum deles a nenhum dos outros. Claro que o problema

Encontre um primo no intervalo $[N, N+\log^{17} N ]$

resolve tudo isso.

Peter Shor
fonte

Para ser preciso, qual é a versão de decisão desses problemas que você tem em mente? Obrigado.

usul

@usul: Eu não tenho uma versão de decisão desses problemas em mente. Eu preciso? Sei que, tecnicamente, o BPP consiste apenas em problemas de decisão. Na maioria das vezes, os problemas de decisão e os problemas de função são mais ou menos equivalentes, o que significa que você pode considerar apenas problemas de decisão sem perda de generalidade. Não sei se isso é verdade para esta pergunta e não sei se o OP se importa apenas com problemas de decisão ou não.

Peter Shor

Só estou perguntando, porque não sei exatamente quando surgem sutilezas importantes. Eu acho que deve haver alguns problemas de função que são conhecidos incondicionalmente em "BPP" e não em "P", por exemplo, produzem uma sequência de complexidade de Kolmogorov (?). Por isso, pensei que a pergunta apontaria para problemas de decisão e fiquei imaginando se uma versão de decisão válida da sua resposta (dado o conhecimento atual) seria, por exemplo, "existe um primo em ?"

n

$n$

[N, 5 N / 4]

$[N,5N/4]$

usul 01/01

@usul: Para a pergunta: "existe um primo em ?", sabe-se que existe um algoritmo de tempo constante. Parece: Diga "sim" quando e verifique explicitamente quando . Você precisa de alguma teoria dos números para provar que funciona.

[N, 5 N / 4]

$[N, 5N/4]$

N > 10^{6}

$N > 10^6$

N \leq 10^{6}

$N \leq 10^6$

Peter Shor

Ok, claro / ótimo. Acho que concordo com o comentário de Kaveh nesta pergunta de que um problema natural de decisão correspondente é, dado , existe um primo em ?

a, b

$a,b$

[a, b]

$[a,b]$

usul

Existe um uso particular da aleatoriedade que é bastante comum na complexidade parametrizada, que envolve o lema do isolamento ou o lema de Schwartz-Zippel . Grosso modo, envolve definir uma grande enumeração de soluções em potencial e argumentar que todas as não soluções "emparelham" (por exemplo, são contadas duas vezes) enquanto as soluções desejadas são contadas apenas uma vez. Então, usa-se o lema de isolamento para produzir uma situação com apenas uma solução menor, ou define um grande polinômio formal correspondente sobre GF e usa Schwartz-Zippel para testar se existe algum termo não emparelhado. (Tenho certeza de que há uma boa visão geral ou pesquisa por aí, mas no momento isso me escapa.) $(2^\ell)$

Dito isto, só consigo pensar em dois casos em que esse uso levaria a uma diferença entre BPP e P.

O primeiro é o algoritmo recente para os dois caminhos disjuntos mais curtos ( PDF do autor ), Björklund e Husfeldt, ICALP 2014.

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

Magnus Wahlström
fonte

Não sou especialista, mas talvez alguns exemplos (não tão naturais?) Possam ser derivados diretamente usando a técnica de reduzir deterministicamente os problemas de pesquisa de BPP para problemas de decisão de BPP , apresentados em:

Oded Goldreich, em um mundo de P = BPP. Estudos em Complexidade e Criptografia 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})$

O teorema pode ser estendido a problemas gerais de construção, por exemplo (veja Corolário 3.9 ), considere o problema de encontrar um primo em um intervalo suficientemente grande:

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

O algoritmo aleatório é executado no tempo polinomial esperado; nenhum algoritmo de tempo polinomial determinístico é conhecido; mas se BPP = P, esse algoritmo de tempo polinomial determinístico deve existir (porque pode ser reduzido a um problema de decisão de BPP).

Marzio De Biasi
fonte