A aleatoriedade nos compra alguma coisa dentro de P?

Seja a classe dos problemas de decisão que possuem um algoritmo aleatório delimitado com erro de dois lados, executando no tempo . $\mathsf{BPTIME}(f(n))$ $O(f(n))$

Conhecemos algum problema tal que mas ? A sua inexistência é comprovada? $Q \in \mathsf{P}$ $Q \in \mathsf{BPTIME}(n^k)$ $Q \not \in \mathsf{DTIME}(n^k)$

Esta pergunta foi feita no cs.SE aqui , mas não obteve uma resposta satisfatória.

cc.complexity-theory ds.algorithms randomized-algorithms derandomization aelguindy
fonte

(1) BPP (f (n)) é geralmente indicado como BPTIME (f (n)). (2) Na configuração da complexidade computacional, acredito que isso esteja aberto. (Muitos exemplos são conhecidos nas configurações de complexidade da consulta e da complexidade da comunicação.) (3) Se sua inexistência já estivesse comprovada, já saberíamos que P = BPP.

Tsuyoshi Ito

A propósito, na pergunta em cs.stackexchange.com, você tem algum mal-entendido sobre a relação entre BPTIME e ZPTIME, e isso pode ser parte do motivo pelo qual você não recebeu uma resposta satisfatória.

Tsuyoshi Ito

@TsuyoshiIto Obrigado, eu não concordo que se provar inexistência então sabemos

, estou restringindo a configuração para problemas em

. Talvez,

, enquanto

P = B P P

$P=BPP$

P

$P$

B P T I M E (n^{k}) \cap P = D T I M E (n^{k})

$BPTIME(n^k) \cap P = DTIME(n^k)$

em geral, estou perdendo alguma coisa? Você também pode agradar a ponto do meu mal-entendido sobre

, talvez eu perdi uma resposta satisfatória, na verdade ..

B P T I M E (n^{k}) \neq D T I M E (n^{k})

$BPTIME(n^k) \neq DTIME(n^k)$

B P T I M E

$BPTIME$

Z P T I M E

$ZPTIME$

aelguindy

Sua pergunta não diz que você restringe o problema Q para estar dentro de P. Se essa é sua intenção, edite-a.

Tsuyoshi Ito

Para aproximar a mediana 1 de um espaço métrico finito com poucas consultas à função de distância, um ponto aleatório fornece uma aproximação 2 em expectativa e uma aproximação (2 + eps) com boa probabilidade. Mas nenhum algoritmo determinístico que consulta a função de distância

vezes pode fazer melhor do que uma aproximação de 4. [ Chang 2013 ]

o (n^{2})

$o(n^2)$

Neal Young

Respostas:

Outro exemplo é estimar o volume de um poliedro em altas dimensões. Existe um limite inferior incondicional nas estratégias determinísticas para aproximar o volume até um fator exponencial, mas há um FPRAS para o problema.

Atualização: o documento relevante é (link para PDF ):

I. Barany e Z. Furedi. A computação do volume é difícil, Discrete and Computational Geometry 2 (1987), 319-326.

Suresh Venkat
fonte

Você poderia fornecer referência para o limite inferior incondicional?

T ....

referência adicionada.

Suresh Venkat

Problema : Uma matriz consiste em 1s e 0s. Encontre um tal que seja 1. $A[1..2n]$ $n$ $n$ $i$ $A[i]$

Você tem permissão para consultar 'Qual número está presente em '? Cada consulta leva tempo constante. $A[i]$

Solução : Algoritmo Aleatório: Escolha um índice aleatório verifique se é 1. O número esperado de consultas é 2, mas qualquer algoritmo determinístico deve fazer pelo menos consultas. Portanto, o limite superior aleatório é estritamente melhor que o limite inferior determinístico neste modelo. $i$ $A[i]$ $n$

Este é um exemplo da complexidade da consulta a que Tsuyoshi estava se referindo no comentário.

Jagadish
fonte

Qualquer algoritmo determinístico deve fazer pelo menos

consultas no pior caso .

n

$n$

Argentpepper

O que você quer dizer com "atualmente não conhecemos nenhuma prova não trivial de limite inferior para qualquer problema no NP (e muito menos em P)"?

Kristoffer Arnsfelt Hansen

Talvez eu tenha usado a palavra 'não trivial' desleixada. Eu quis dizer 'Atualmente, não podemos provar um limite inferior incondicional de

para

para SAT ou qualquer problema no NP'. Isso está correto?

Ω (n^{k})

$\Omega(n^k)$

k > 0

$k>0$

Jagadish

Bem, talvez não por problemas "agradáveis", como o SAT; mas lembre-se de que temos limites inferiores para outros problemas dos teoremas da hierarquia de tempo. E a pergunta não é sobre problemas "legais", mas sobre classes de complexidade.

Kristoffer Arnsfelt Hansen

Ah, certo. Supus que o OP estivesse interessado em problemas naturais. Eu editei minha resposta.

Jagadish

Dado um matriz de compensação por uma matriz de soma-zero com pagamentos em [0,1], estimar o valor de jogo dentro de um aditivo . $n\times n$ $\epsilon$

Esse problema possui um algoritmo aleatório que é executado no tempo , que (provavelmente) nenhum algoritmo determinístico pode corresponder a [ GK95 ]. $O(n\log^2(n)/\epsilon^2)$

Veja também Algoritmos aleatórios eficientes e simples, onde o determinismo é difícil .

Neal Young
fonte