Medida de recurso delimitado: diferenças entre revisões

'''Lutz'sA medida de recurso delimitado de Lutz''' é uma generalização parada [[Medida de Lebesgue|Medida de Lebesguere]] e para [[Classe de complexidade|classes de complexidade]]. Foi originalmente desenvolvidodesenvolvida por [[Jack Lutz]]. Assim como a medida de Lebesgue dá um método para quantificar o tamanho de subconjuntos do [[Espaço euclidiano|Espaço euclideano]] <math>\R^n</math>, 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 (complexidade)|P]] (o conjunto de todos os problemas de decisão solúveis em [[Complexidade de tempo#Tempo Polinomial|tempo polinomial]]) não é igual aà classe de complexidade [[NP (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 versus NP|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 (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_(matemática)|medida teórica]], "muito maior que P".

(Esta é a definição original de Ville de um martingale, posteriormente prorrogadoestendida por [[Joseph Leo Doob]].) MartingaleUm martingale ''d é'' bem sucedido por uma sequência <math>S\in\{0,1\}^\infty</math> se <math>\limsup_{n\to\infty} d(S \upharpoonright n) = \infty,</math> quandoonde <math>S \upharpoonright n</math> são os primeiros ''n'' bits de ''S''. MartingaleUm martingale '''é bem sucedido''' em um conjunto de sequências <math>X\subseteq\{0,1\}^\infty</math> se for bem sucedido em cada sequência de ''X''.

Intuitivamente, um martingale é um apostador que começa com algumauma 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 <math>w\in\{0,1\}^*</math>, 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 qual lugaronde deve apostar, por causa da natureza restrita do jogo, o conhecimento, os valores ''d(w), d(w0)'' e ''d(W1w1)'' é suficiente para calcular as apostas ''d'' colocadoscolocadas 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 teoria da ''filtração'' na teoria [[Martingale (teoria da probabilidade)|generalizada de martingalemartingales]]).

O resultado chave dasrelacionando medida relativas paraa martingaismartingales é a observação de Ville de que um conjunto Ville <math>X\subseteq\{0,1\}^\infty</math> tem medida de Lebesgue 0 se e somente se houver um martingale bem sucedido martingale 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 consideradoconsiderou restringindorestringir o poder computacional do martingale. Por exemplo, se em vez de permitir que qualquer martingale, exigimos que o martingale serseja computável em tempo polinomial, eme aí seguidaentã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. Nós definimosDefinimos um conjunto decomo tertendo p-medida 1 se seu complemento tem p-medida 0. Por exemplo, provandoprovar a conjectura acima mencionadosupracitada, que a NP não tem p-medida 0, isso leva asignifica provar que emnenhum tempomartingale nãode tempo polinomial martingale é bem sucedido em todostoda a osclasse NP.

Um problema estáé '''quase completo''' para uma [[Classe de complexidade]] C se ele estiver em C e "muitos" outros problemas de C são reduzíveisredutí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.