Mostrar código-fonte de Complexidade de caso genérico

'''Complexidade de Caso Genérico''' é uma subárea da [[Complexidade computacional|teoria da complexidade computacional]] que estuda a complexidade de problemas computacionais na "maioria das entradas".

Complexidade de Caso Genérico é uma forma de medir a complexidade de um [[problema computacional]] desprezando um pequeno conjunto de  entradas não representativas e aplicando a[[Complexidade de pior caso| complexidade do pior caso]]  nas entradas restantes.
Pequeno é definido em termos de densidade assintótica.
A aparente eficácia da complexidade de caso genérico se dá porque, para uma ampla variedade de  problemas computacionais concretos, as instâncias mais difíceis parecem ser raras. Os casos típicos, são relativamente fáceis.

Esta abordagem da complexidade foi originada em [[Teoria combinatória de grupos|teoria combinatória dos grupos]], que tem uma tradição computacional  que remonta ao início do século passado.
A noção  de complexidade genérica foi introduzida em um artigo<ref name="KMSS">I. Kapovich, A. Myasnikov, P. Schupp and V. Shpilrain, ''[[arxiv:math/0203239|Generic case complexity, decision problems in group theory and random walks]]'', J. Algebra, vol 264 (2003), 665–694.</ref>  de 2003 onde os autores mostraram que, para uma grande classe de grupos gerados finitamente  a complexidade de tempo genérica de alguns problemas clássicos  [[Problema de decisão|de decisão]] provenientes da  teoria combinatória dos grupos, conhecidamente, o [[Problema da palavra para grupos|problema da aceitação de uma palavra]], problema da conjugação e o problema da pertinência, são lineares.

Uma introdução detalhada da  complexidade de caso genérico pode ser encontrado nas pesquisas.<ref name="GMMU">R. Gilman, A. G. Miasnikov, A. D. Myasnikov, and A. Ushakov, ''Generic Case Complexity'', unpublished first draft of a book, 143 pages.
</ref><ref>R. Gilman, A. G. Miasnikov, A. D. Myasnikov, and A. Ushakov, ''[http://www.stevens.edu/algebraic/Files/GC/gc_survey.pdf Report on generic case complexity]'', Herald of Omsk University, Special Issue, 2007, 103–110.</ref>

== Definições básicas ==

=== Densidade Assintótica ===
Seja I um [[conjunto infinito]] de entradas para um problema computacional.

'''Definição 1.''' Uma função de tamanho em ''I'' é um mapeampento <math>\sigma:I\to \mathbb{N}</math> com alcance infinito.
A bola de raio ''n'' é <math>B_n=\{x\in I \mid \sigma(x)\le n \}</math>.

Se as entradas são codificadas como cadeias sobre um alfabeto finito, o tamanho pode ser o comprimento da cadeia.

Seja <math>\{\mu_n\}</math>  um conjunto de [[Distribuição de probabilidade|distribuições de probabilidade]] , onde <math>\mu_n</math>
é uma distribuição de probabilidade sobre <math>B_n</math>.
Se as bolas <math>B_n</math> são finitas, então, cada um <math>\mu_n</math> pode ser tomado para
ter distribuição equiprovável, que é o caso mais comum. Observe que apenas finitamente muitos
<math>B_n</math>'s pode ser vazios ou ter <math>\mu_n(B_n) = 0</math>; nós os ignoramos.

'''Definição 2.''' A densidade assintótica de um subconjunto <math>X \subset I</math>é
<math>\rho(X) = \lim_{n \to \infty}\mu_n(X \cap B_n)</math> quando este limite existe.

Quando as bolas <math>B_n</math> são finitas e <math>\mu_n</math> é a medida equiprovável.
: <math>\rho(X)=\lim \frac{|X\cap B_n|}{|B_n|}.</math>
Neste caso muitas vezes é conveniente a utilização de esferas <math>I_n=\{x\in I\mid \sigma(x)=n\}</math> em vez de bolas e
definir <math>\rho'(X)=\lim \frac{|X\cap I_n|}{|I_n|}</math>. Um argumento usando [[Teorema de Stolz-Cesàro|o teorema de Stolz]] mostra que <math>\rho(X)</math>
existe se <math>\rho'(X)</math>  existe, e, nesse caso, eles são iguais.

'''Definição 3''' <math>X\subseteq I</math> é genérico se <math>\rho(X)=1</math> e insignificante se <math>\rho(X)=0</math>.
''X'' é exponencial (superpolinomialmente) genérico se a convergência para o limite na Definição 2 é exponencial (superpolinomial) rápido, etc.

Um subconjunto genérico  ''X'' é assintoticamente grande. Se ''X'' aparece grande na prática, depende
em quão rápido <math>\mu_n(X\cap B_n)</math> converge para 1. Convergência superpolinomial  parece ser rápido o suficiente.

=== Classes de complexidade Genérica ===
'''Definição 4''' Um [[algoritmo]] está em ''GenP'' (genericamente em tempo polinomial) se ele nunca dá respostas incorretas e se
dá respostas corretas em [[Complexidade de Tempo|tempo polinomial]] em um conjunto genérico de entradas. O problema está em ''GenP'' se ele admite um algoritmo em ''GenP''. Da mesma forma, para ''GenL'' (genericamente tempo linear), ''GenE''(genericamente
tempo exponencial com um linear expoente) ''GenExp'' (genericamente tempo exponencial), etc.
''ExpGenP'' é a subclasse de ''GenP'' para o qual o conjunto genérico é exponencialmente genérico.

Mais geralmente para qualquer f : \mathbb{N} \to \mathbb{N} podemos definir a classe Gen(f) correspondente a complexidade de tempo O(f) em um conjunto genérico de entrada.

'''Definição 5.''' Um algoritmo resolve um problema genericamente se ele nunca fornece respostas incorretas e se ele dá respostas corretas sobre um conjunto genérico de entradas. Um problema é genericamente solúvel se ele é resolvido genericamente por algum algoritmo.

== Teoria e aplicações ==

=== Problemas em teoria de grupos combinatórios ===
* Os conhecidos [[Problema indecidível|problemas indecidíveis]]: aceitação de palavras por máquina de Turing, conjugação e pertinência são genericamente em tempo polinomial.<ref name="KMSS">I. Kapovich, A. Myasnikov, P. Schupp and V. Shpilrain, ''[[arxiv:math/0203239|Generic case complexity, decision problems in group theory and random walks]]'', J. Algebra, vol 264 (2003), 665–694.</ref>
* O problema da parada e o problema da conjugação enquanto  [[problema de busca]] estão em ''GenP''  para todos os grupos finitamente apresentados.<ref>A. Ushakov, ''Dissertation'', City University of New York, 2005.</ref>

* O conhecido  procedimento enumeração de coclasses  admite um limite computável  superior para um conjunto genérico de entradas.<ref>R. Gilman, ''Hard problems in group theory'', talk given at the International Conference
on Geometric and Combinatorial Methods in Group Theory and Semigroup Theory,
May 18, 2009.</ref>

* O algoritmo Whitehead para testar se  um elemento de um grupo livre é ou não  mapeado para outra através de um automorfismo tem o limite superior para o pior caso em custo exponencial , mas funciona bem na prática. O algoritmo é mostrado na ''GenL''.<ref>I. Kapovich, P. Schupp, V. Shpilrain, ''[[arxiv:math.GR/0303386|Generic properties of Whiteheads algorithm and isomorphism rigidity of random one-relator groups]]'', Pacific J. Math. 223 (2006)</ref>

* O problema da conjugação  em  extensões HNN pode ser insolúvel, mesmo para [[Grupo livre|grupos livres]]. No entanto, é genericamente de tempo cúbicos .<ref>A.V. Borovik, A.G. Myasnikov, V.N. Remeslennikov, ''[[arxiv:0903.3754|Generic complexity of the conjugacy problem in HNN-extensions and algorithmic stratification of Miller's groups]]'',
Internat. </ref>

=== A problema da parada e o problema da correspondência de Post ===
* O [[problema da parada]] para a [[máquina de Turing]] com uma fita de lado é facilmente decidível na maioria das vezes; ele está em ''GenP''<ref>J. D. Hamkins and A. Miasnikov, ''[[arxiv:math/0504351|The halting problem is decidable on a set of asymptotic probability one]]'', Notre Dame J. Formal Logic 47 (2006), 515–524.
</ref>
A situação para fita de dois lados é desconhecida. No entanto, há um tipo de limite inferior para máquinas de ambos os tipos.
A suspensão problema não está em ''ExpGenP'' para qualquer modelo de máquina de Turing,<ref>A. Miasnikov and A. Rybalov, ''[http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.jsl/1208359065 Generic complexity of undecidable problems]'', J. Symbolic Logic 73 (2008), 656–673.
</ref><ref>A. Rybalov, ''[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-4N2TS51-3&_user=605441&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1052347431&_rerunOrigin=google&_acct=C000029138&_version=1&_urlVersion=0&_userid=605441&md5=8bee4d70a78ff9d14450f6bc7a993984 On the strongly generic undecidability of the halting problem]'', Theoret. </ref>
* O [[problema da correspondência de Post]] está em ''ExpGenP''.<ref name="GMMU">R. Gilman, A. G. Miasnikov, A. D. Myasnikov, and A. Ushakov, ''Generic Case Complexity'', unpublished first draft of a book, 143 pages.
</ref>

=== A aritmética de Presburger ===
O [[problema de decisão]] para [[Aritmética de Presburger|a aritmética de Presburger]] admite uma dupla exponencial no pior caso como limite inferior<ref>M. J. Fischer and M. O. Rabin, ''Super-Exponential Complexity of Presburger Arithmetic'', Proceedings of the SIAM-AMS Symposium in Applied Mathematics 7 (1974) 2741.</ref> e um triplo exponencial no pior caso para limite superior. A complexidade genérica não é conhecida, mas sabe-se que o problema não está no ''ExpGenP''.<ref>A. Rybalov, ''Generic complexity of Presburger arithmetic'', 356–361 in Second International Symposium on Computer Science in Russia, CSR 2007, Lecture Notes in Computer Science 4649, Springer 2007.</ref>

=== Problemas NP-completos ===
Como é sabido que os [[NP-completo|problemas NP-completos]] podem ser, na média, fáceis, não é uma surpresa que vários deles sejam genericamente fáceis também.
* Os três [[Satisfatibilidade|problemas de satisfiabili]]<nowiki/>dade estão em ''ExpGenP''.<ref>R. Gilman, A. G. Miasnikov, A. D. Myasnikov, and A. Ushakov, Report on generic
case complexity, Herald of Omsk University, Special Issue, 2007, 103–110.</ref>
* O [[Problema da soma dos subconjuntos|problema da soma de subconjuntos]] está em ''GenP''.<ref name="GMMU">R. Gilman, A. G. Miasnikov, A. D. Myasnikov, and A. Ushakov, ''Generic Case Complexity'', unpublished first draft of a book, 143 pages.
</ref>

=== Funções unidirecionais ===
Há uma versão de complexidade genérica para uma [[Função de mão única|função unidirecional]]<ref>A. D. Myasnikov, ''[[arxiv:0802.3734|Generic Complexity and One-Way Functions]]'', Groups, Complexity and Cryptography, 1, (2009), 13–31.</ref> , o qual produz a mesma classe de funções, mas permite considerar premissas de segurança diferentes do habitual.

=== Criptografia de chave pública ===
Uma série de artigos<ref>R. Gilman, A. G. Miasnikov, A. D. Myasnikov, and A. Ushakov, ''New developments in commutator key exchange'', Proc. </ref><ref>A. G. Myasnikov, V. Shpilrain, A. Ushakov, ''A practical attack on a braid group based cryptographic protocol'', in Lecture Notes in Computer Science, 3621, Springer Verlag,
2005, 86–96.</ref><ref>A. D. Myasnikov, and A. Ushakov, ''Length based attack and braid groups: cryptanalysis of Anshel–Anshel–Goldfeld key exchange protocol'', in Public Key Cryptography PKC 2007, 76–88, Lecture Notes in Comput. </ref> é dedicado à [[criptoanálise]] do protocolo de troca de chaves de Anshel–Anshel–Goldfeld, cuja segurança é baseada em suposições sobre o grupo de tranças . Esta série culmina em Miasnikov e Ushakov (2008)<ref>A. G. Miasnikov and A. Ushakov, ''Random subgroups and analysis of the length-based and quotient attacks'', Journal of Mathematical Cryptology, 2 (2008), 29–61.</ref> , que aplica as técnicas de caso  de complexidade genérica para obter uma análise completa do ataque baseado em comprimento e as condições sob as quais ele trabalha. O  ponto de vista genérico também sugere um novo tipo de ataque chamado o quociente de ataque, e uma versão mais segura do protocolo de Anshel–Anshel–Goldfeld.

=== Lista de resultados teóricos gerais ===
* Um famoso [[teorema de Rice]] afirma que, se ''F'' é um subconjunto do conjunto de funções parcialmente computáveis  de <math>\mathbb{N}</math> a <math>\{0,1\}</math>, então a menos que o ''F'' ou o seu complemento seja vazia, o problema de decidir se quer ou não uma determinada [[máquina de Turing]] computa uma função ''F'' é indecidível. O seguinte teorema fornece uma versão genérica.
'''Teorema 1 de'''<ref>A. Miasnikov and A. Rybalov, ''Generic complexity of undecidable problems'', J. Symbolic Logic 73 (2008), 656–673.
</ref> Seja ''I'' o conjunto de todas as máquinas de Turing. Se ''F'' é um subconjunto do conjunto de todos as funções parcialmente computáveis de <math>\mathbb{N}</math>  em \mathbb{N}, tais que ''F'' e seu complemento são ambos não-vazios, então o problema de decidir se  uma dada máquina de Turing computa uma função a partir de
''F'' ou näo é indecidível sobre qualquer subconjunto exponencialmente genérico  de I.
* Os seguintes teoremas são a partir de:<ref name="KMSS">I. Kapovich, A. Myasnikov, P. Schupp and V. Shpilrain, ''[[arxiv:math/0203239|Generic case complexity, decision problems in group theory and random walks]]'', J. Algebra, vol 264 (2003), 665–694.</ref>
'''Teorema 2''' O conjunto de [[Linguagem formal|linguagens formais]] que são chamados genericamente de computáveis tem medida zero.

'''Teorema 3''' Há uma hierarquia infinita  de [[Classe de complexidade|classes de complexidade]] genérica. Mais precisamente
para uma apropriada função de complexidade ''f'', <math>Gen(f) \subsetneq Gen(f^3)</math>.
* O próximo teorema mostra que, assim como há o caso médio completo de problemas dentro da distribuição dos problemas NP,
há também o caso genérico completo de  problemas. Os argumentos no caso genérico são semelhantes
aqueles no caso médio, e caso genérico completo problema é também o caso médio completo.
É  o problema da parada limitado distributivo.

'''Teorema 4'''<ref name="GMMU">R. Gilman, A. G. Miasnikov, A. D. Myasnikov, and A. Ushakov, ''Generic Case Complexity'', unpublished first draft of a book, 143 pages.
</ref> Há uma noção de [[redução em tempo polinomial]] genérica com relação ao
qual o problema da parada limitado distributivo é completo dentro da classe distributiva dos problemas NP.

== Comparações com trabalhos anteriores ==

=== Tempo quase polinomial ===
Meyer e Paterson<ref>A. R. Meyer and M. S. Paterson, ''With what frequency are apparently intractable''
problems difficult?'', M.I.T. Technical Report, MIT/LCS/TM-126, February, 1979.''
</ref> definiram um algoritmo para ser em tempo quase polinomial, ou TQP, se ele para
dentro de ''p(n)'' passos, mas com ''p(n)'' entradas de tamanho ''n''. Claramente, os algoritmos TQP  estão incluídos no nosso
classe ''GenP''. Temos visto que vários problemas [[NP-completo|NP-completos]] em ''GenP'', mas Meyer e Paterson
mostram que esse não é o caso para o TQP. Eles provam que um problema NP-completo  é redutível a
um problema em  APT se e somente se [[P versus NP|P = NP]]. Assim o TQP parece ser muito mais restritiva do que ''GenP''.

=== Complexidade de caso médio ===
Complexidade de caso genérico é semelhante à [[complexidade de caso médio]]. No entanto, existem algumas diferenças significativas.
Complexidade de caso genérico é uma medida direta do desempenho de um algoritmo na maioria das entradas, enquanto complexidade de caso médio
dá uma medida do equilíbrio entre instâncias fáceis e difíceis. Além disso Complexidade de caso genérico, naturalmente, aplica-se a [[Problema indecidível|problemas indecidíveis]].

Suponha que <math>\mathcal{A}</math> é um algoritmo cuja [[Complexidade de Tempo|complexidade de tempo]], <math>T:I\to \mathbb{N}</math> é na média polinomial em <math>\mu</math>.
O que podemos inferir sobre o comportamento de <math>\mathcal{A}</math> com entradas típicas?

'''Exemplo 1''' Seja ''I'' o conjunto de todas as palavras sobre <math>\{0,1\}</math> e defina o tamanho <math>\sigma(w)</math> como sendo o comprimento da palavra,
<math>|w|</math>. Defina <math>I_n</math> como sendo o conjunto das palavras de comprimento ''n'', e assuma que todos  <math>\mu_n</math> tem medida equiprovável. Suponha que ''T(w)=n para todas as palavras exceto uma em cada'' <math>I_n</math>, e <math>T(w)=2^{2^n}</math> em palavras excepcionais.

Neste exemplo ''T'' certamente é polinomial em entradas típicas, porém, ''T'' não é polinomial na média. ''T'' está ''GenP''.

'''Exemplo 2''' Mantenha ''I'' e <math>\sigma(w) = |w|</math> como antes, mas defina <math>\mu(w)= 2^{-2|w|-1}</math> e
<math>T(w) = 2^{|w|}</math>. ''T'' é polinomial na média apesar de ser exponencial em entrada tipicas. ''T'' não está em ''GenP''.

Nesses dois exemplos a complexidade genérica é mais proximamente relacionada ao comportamento típico das entradas do que à complexidade de caso médio. A complexidade de caso médio mede outra coisa: o equilíbrio entre as frequências com que ocorrem instâncias difíceis e o grau de dificuldade.<ref>Y. Gurevich, ''The challenger-solver game: variations on the theme of P =?''</ref><ref>R. Impagliazzo, ''A personal view of average-case complexity'', in Proceedings of the
10th Annual Structure in Complexity Theory Conference - SCT 1995, IEEE Computer
Society, 1995, page 134.</ref>
A grosso modo um algoritmo que é de tempo polinomial na média pode ter apenas uma fração subpolinomial de entradas que requerem tempo superpolinomial para computar.

No entanto, em alguns casos de complexidade genérica e média  são bastante próximos uns dos outros.
Uma função <math>f:I\rightarrow\mathbb{R}^+</math> é polinomial em <math>\mu</math>média nas esferas se existe um <math>k \geq 1</math> tal que <math>\sum_{w\in I_n} f^{1/k}(w) \mu_n(w) = O(n)</math> , onde <math>\{\mu_n\}</math>
é o conjunto induzido por <math>\mu</math>. Se ''f'' é polinomial em <math>\mu</math>média nas esferas, o ''f ''é
polinômial em <math>\mu</math>média, e para muitas distribuições <ref>Y. Gurevich, ''Average case completeness'', J. of Computer and System Science, 42
(1991), 346–398.
</ref>

'''Teorema''' 5<ref name="GMMU">R. Gilman, A. G. Miasnikov, A. D. Myasnikov, and A. Ushakov, ''Generic Case Complexity'', unpublished first draft of a book, 143 pages.
</ref> Se uma função <math>f:I\rightarrow \mathbb{R}^+</math> é polinomial em <math>\mu</math>média nas esferas, então, ''f''
é genericamente polinomial em relação à densidade esférica assintótica  <math>\rho'</math>.

'''Teorema''' 6<ref name="GMMU">R. Gilman, A. G. Miasnikov, A. D. Myasnikov, and A. Ushakov, ''Generic Case Complexity'', unpublished first draft of a book, 143 pages.
</ref> Suponha que um algoritmo completo <math>\mathcal{A}</math> tem tempo limitado a subexponential ''T'' e uma parte de um algoritmo <math>\mathcal{B}</math>
para o mesmo problema está em ''ExpGenP'' com respeito ao conjunto <math>\{\mu_n\}</math> correspondente a uma medida da probabilidade <math>\mu</math>
nas entradas ''I ''para <math>\mathcal{A}</math>. Então, há um algoritmo que é tem complexidade de tempo <math>\mu</math>-média.

=== Algoritmos heurísticos sem erro ===
Em 2006, em um artigo, Bogdanov e Trevisan chegaram perto de definir o caso de complexidade genérica.<ref>A. Bogdanov, L. Trevisan, ''Average-case Complexity'', Found. </ref> Em vez de algoritmos parciais, eles consideram os assim chamados algoritmos heurísticos sem erros. Estes são algoritmos que podem não parar com a saída "?". A classe ''AvgnegP'' é definida para consistir em todos os  algoritmos heurísticos sem erros ''A'' que executam em tempo polinomial e para os quais a
probabilidade de falha <math>I_n</math> é insignificante, i.é., converge superpolinomialmente rápido para 0.
''AvgnegP'' é um subconjunto de ''GenP''. Algoritmos heurísticos sem erro são essencialmente os mesmos que os algoritmos com
falhas benignas  definidos por Impagliazzo, onde  tempo polinomial em algoritmos medianos, são
caracterizados em termos dos chamados algoritmo de esquemas benignos.

== Referências ==
{{Reflist}}
[[Categoria:Teoria da complexidade computacional]]