Medida de recurso delimitado

A medida de recurso delimitado de Lutz é uma generalização da Medida de Lebesgue para classes de complexidade. Foi originalmente desenvolvida por Jack Lutz. Assim como a medida de Lebesgue dá um método para quantificar o tamanho de subconjuntos do Espaço euclideano $\mathbb {R} ^{n}$, a medida de recurso delimitado dá um método para classificar o tamanho de subconjuntos de classes de complexidade.

Por exemplo, os cientistas da computação em geral acreditam que a classe de complexidade P (o conjunto de todos os problemas de decisão solúveis em tempo polinomial) não é igual à classe de complexidade NP (o conjunto de todos os problemas de decisão verificável, mas não necessariamente solucionável, em tempo polinomial). Uma vez que P é um subconjunto de NP, isso significaria que NP contém mais problemas do que P. Uma hipótese mais forte que indica que "P é diferente de NP" é a afirmação "NP não tem p-medida 0". Aqui, p-medida é uma generalização da medida de Lebesgue para os subgrupos da classe de complexidade E, em que P é contida. P é conhecida por ter p-medida de 0, e assim a hipótese de "NP não tem p-medida 0" implica não somente que NP e P são desiguais, mas que NP é, em sentido de medida teórica, "muito maior que P".

Definição

$\{0,1\}^{\infty }$ é o conjunto de todas sequências binárias infinitas. Nós podemos ver um número real no intervalo unitário como uma sequência binária infinita, considerando sua expansão binária. Nós também podemos ver uma linguagem (um conjunto de cadeias binárias) como uma sequência binária infinita, definindo o n-ésimo bit da sequência para 1 se e somente se a string binária n-ésima (em ordem lexicográfica) está contida na língua. Assim, conjuntos de números reais no intervalo unitário e classes de complexidade (que são conjuntos de linguagens) podem ambos ser visto como conjuntos de sequências binárias infinitas, portanto, as técnicas de medidas utilizadas para medir o tamanho dos conjuntos de números reais podem ser aplicado para medir classes de complexidade. No entanto, uma vez que cada classe de complexidade contável contém apenas um número contável de elementos (porque o número de linguagens computáveis é contável), cada classe de complexidade tem medida de Lebesgue 0. Assim, para fazer a medida dentro de classes de complexidade, é preciso definir uma medida alternativa que funciona significativamente em conjuntos contáveis de sequências infinitas. Para que esta medida seja significativa, ela deve refletir algo sobre a definição subjacente de cada classe de complexidade, ou seja, que eles são definidos por problemas computacionais que pode ser resolvido dentro de um determinado recurso vinculado.

O fundamento da medida de recurso delimitado é a formulação martingale de Ville. Martingale é uma função $d:\{0,1\}^{*}\to [0,\infty )$ de tal forma que, para todas as sequências finitas w,

$d(w)={\frac {d(w0)+d(w1)}{2}}$.

(Esta é a definição original de Ville de um martingale, posteriormente estendida por Joseph Leo Doob.) Um martingale d é bem sucedido por uma sequência $S\in \{0,1\}^{\infty }$ se $\limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,$ onde $S\upharpoonright n$ são os primeiros n bits de S. Um martingale é bem sucedido em um conjunto de sequências $X\subseteq \{0,1\}^{\infty }$ se for bem sucedido em cada sequência de X.

Intuitivamente, um martingale é um apostador que começa com uma certa quantidade finita de dinheiro (digamos, um dólar). Ele lê uma sequência de bits por tempo indeterminado. Depois de ler o prefixo finito $w\in \{0,1\}^{*}$, aposta parte de seu dinheiro que o próximo bit será 0, e a parte restante do seu dinheiro que o próximo bit será um 1. Ele dobra o que foi apostado no bit que apareceu, e ele perde o dinheiro colocado no bit que não apareceu. Deve apostar todo o seu dinheiro, mas pode apostar de forma que não vai ganhar nem perder nada, colocando a metade de seu dinheiro em cada bit. Para um martingale d, d(w) representa a quantidade de dinheiro d que tem depois de ler a cadeia w. Embora a definição de um martingale tem o martingale calculando quanto dinheiro ele vai ter, em vez de onde deve apostar, por causa da natureza restrita do jogo, o conhecimento, os valores d(w), d(w0) e d(w1) é suficiente para calcular as apostas d colocadas em 0 e 1 depois de ver a cadeia w. O fato de que o martingale é uma função que recebe como entrada a sequência visto até agora significa que as apostas são apenas uma função dos bits já lidos nenhuma outra informação pode afetar as apostas (sendo as restantes a chamada filtração na teoria generalizada de martingales).

O resultado chave relacionando medida a martingales é a observação de Ville de que um conjunto $X\subseteq \{0,1\}^{\infty }$ tem medida de Lebesgue 0 se e somente se houver um martingale bem sucedido em X. Assim, podemos definir um conjunto de medida 0 a ser aquele para o qual existe um martingale que é bem sucedido em todos os elementos do conjunto.

Para estender este tipo de medida para classes de complexidade, Lutz considerou restringir o poder computacional do martingale. Por exemplo, se em vez de permitir qualquer martingale, exigimos que o martingale seja computável em tempo polinomial, e aí então, obtém-se uma definição de p-medida: um conjunto de sequências tem p-medida 0 se houver um martingale computável em tempo polinomial que é bem sucedido no conjunto. Definimos um conjunto como tendo p-medida 1 se seu complemento tem p-medida 0. Por exemplo, provar a conjectura supracitada, que NP não tem p-medida 0, significa provar que nenhum martingale de tempo polinomial é bem sucedido em toda a classe NP.

Quase completo

Um problema é quase completo para uma Classe de complexidade C se ele estiver em C e "muitos" outros problemas de C são redutíveis a ele. Mais especificamente, o subconjunto de problemas de C, que reduzem o problema é uma medida de um conjunto, em termos da medida de recurso delimitado. Este é um requisito mais fraco do que o problema ser completo para a classe.

Referências

• van Melkebeek, Dieter (2001), Randomness and Completeness in Computational Complexity, ISBN 3-540-41492-4, Springer, consultado em 4 de julho de 2015, cópia arquivada em  🔗 

Ligações externas

• Resource-Bounded Measure Bibliography