Complexidade de caso genérico

Complexidade de Caso Genérico é uma subárea da 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 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 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  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  de decisão provenientes da  teoria combinatória dos grupos, conhecidamente, o 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.

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 $\sigma :I\to \mathbb {N}$ com alcance infinito. A bola de raio n é $B_{n}=\{x\in I\mid \sigma (x)\leq n\}$.

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

Seja $\{\mu _{n}\}$  um conjunto de distribuições de probabilidade , onde $\mu _{n}$ é uma distribuição de probabilidade sobre $B_{n}$. Se as bolas $B_{n}$ são finitas, então, cada um $\mu _{n}$ pode ser tomado para ter distribuição equiprovável, que é o caso mais comum. Observe que apenas finitamente muitos $B_{n}$'s pode ser vazios ou ter $\mu _{n}(B_{n})=0$; nós os ignoramos.

Definição 2. A densidade assintótica de um subconjunto $X\subset I$é $\rho (X)=\lim _{n\to \infty }\mu _{n}(X\cap B_{n})$ quando este limite existe.

Quando as bolas $B_{n}$ são finitas e $\mu _{n}$ é a medida equiprovável.

$\rho (X)=\lim {\frac {|X\cap B_{n}|}{|B_{n}|}}.$

Neste caso muitas vezes é conveniente a utilização de esferas $I_{n}=\{x\in I\mid \sigma (x)=n\}$ em vez de bolas e definir $\rho '(X)=\lim {\frac {|X\cap I_{n}|}{|I_{n}|}}$. Um argumento usando o teorema de Stolz mostra que $\rho (X)$ existe se $\rho '(X)$  existe, e, nesse caso, eles são iguais.

Definição 3 $X\subseteq I$ é genérico se $\rho (X)=1$ e insignificante se $\rho (X)=0$. 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 $\mu _{n}(X\cap B_{n})$ 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 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 problemas indecidíveis: aceitação de palavras por máquina de Turing, conjugação e pertinência são genericamente em tempo polinomial.
• O problema da parada e o problema da conjugação enquanto  problema de busca estão em GenP  para todos os grupos finitamente apresentados.

• O conhecido  procedimento enumeração de coclasses  admite um limite computável  superior para um conjunto genérico de entradas.

• 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.

• O problema da conjugação  em  extensões HNN pode ser insolúvel, mesmo para grupos livres. No entanto, é genericamente de tempo cúbicos .

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

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,

• O problema da correspondência de Post está em ExpGenP.

A aritmética de Presburger

O problema de decisão para a aritmética de Presburger admite uma dupla exponencial no pior caso como limite inferior 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.

Problemas NP-completos

Como é sabido que os 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 problemas de satisfiabilidade estão em ExpGenP.
• O problema da soma de subconjuntos está em GenP.

Funções unidirecionais

Há uma versão de complexidade genérica para uma função unidirecional , 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 é 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) , 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 $\mathbb {N}$ a $\{0,1\}$, 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 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 $\mathbb {N}$  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:

Teorema 2 O conjunto de linguagens formais que são chamados genericamente de computáveis tem medida zero.

Teorema 3 Há uma hierarquia infinita  de classes de complexidade genérica. Mais precisamente para uma apropriada função de complexidade f, $Gen(f)\subsetneq Gen(f^{3})$.

• 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 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 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-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 = 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 problemas indecidíveis.

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

Exemplo 1 Seja I o conjunto de todas as palavras sobre $\{0,1\}$ e defina o tamanho $\sigma (w)$ como sendo o comprimento da palavra, $|w|$. Defina $I_{n}$ como sendo o conjunto das palavras de comprimento n, e assuma que todos  $\mu _{n}$ tem medida equiprovável. Suponha que T(w)=n para todas as palavras exceto uma em cada $I_{n}$, e $T(w)=2^{2^{n}}$ 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 $\sigma (w)=|w|$ como antes, mas defina $\mu (w)=2^{-2|w|-1}$ e $T(w)=2^{|w|}$. 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. 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 $f:I\rightarrow \mathbb {R} ^{+}$ é polinomial em $\mu$média nas esferas se existe um $k\geq 1$ tal que $\sum _{w\in I_{n}}f^{1/k}(w)\mu _{n}(w)=O(n)$ , onde $\{\mu _{n}\}$ é o conjunto induzido por $\mu$. Se f é polinomial em $\mu$média nas esferas, o f é polinômial em $\mu$média, e para muitas distribuições 

Teorema 5 Se uma função $f:I\rightarrow \mathbb {R} ^{+}$ é polinomial em $\mu$média nas esferas, então, f é genericamente polinomial em relação à densidade esférica assintótica  $\rho '$.

Teorema 6 Suponha que um algoritmo completo ${\mathcal {A}}$ tem tempo limitado a subexponential T e uma parte de um algoritmo ${\mathcal {B}}$ para o mesmo problema está em ExpGenP com respeito ao conjunto $\{\mu _{n}\}$ correspondente a uma medida da probabilidade $\mu$ nas entradas I para ${\mathcal {A}}$. Então, há um algoritmo que é tem complexidade de tempo $\mu$-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. 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 $I_{n}$ é 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.