Exemplos do preço da abstração?

A ciência da computação teórica forneceu alguns exemplos do "preço da abstração". Os dois mais proeminentes são para eliminação e classificação gaussiana. Nomeadamente:

• Sabe-se que a eliminação gaussiana é ideal para, digamos, calcular o determinante se você restringir as operações a linhas e colunas como um todo [1]. Obviamente, o algoritmo de Strassen não obedece a essa restrição e é assintoticamente melhor que a eliminação gaussiana.
• Na classificação, se você tratar os elementos da lista como caixas negras que só podem ser comparadas e movimentadas, temos o limite inferior padrão teórico da informação. No entanto, as árvores de fusão superam esse limite, pelo que entendo, o uso inteligente da multiplicação.$n \log n$

Existem outros exemplos do preço da abstração?

Para ser um pouco mais formal, estou procurando exemplos em que um limite inferior é conhecido incondicionalmente em algum modelo fraco de computação, mas é conhecido por ser violado em um modelo mais forte. Além disso, a fraqueza do modelo fraco deve vir na forma de uma abstração , que é reconhecidamente uma noção subjetiva. Por exemplo, não considero a restrição a circuitos monótonos uma abstração. Espero que os dois exemplos acima deixem claro o que estou procurando.

[1] KLYUYEV, VV e NI KOKOVKIN-SHcHERBAK: Na minimização do número de operações aritméticas para a solução de sistemas algébricos lineares de equações. Tradução por GI TEE: Relatório Técnico CS 24, junho t4, t965, Departamento de Ciência da Computação, Universidade de Stanford.

Outro belo exemplo do preço da abstração: codificação de rede . É sabido que, nas configurações multicast, a relação max-flow-min-cut não é de igualdade (o primal e o dual não coincidem). No entanto, os modelos tradicionais assumem um fluxo que é apenas repassado e não "processado" de forma alguma. Com a codificação de rede, você pode superar esse limite combinando inteligentemente os fluxos. Este exemplo foi um grande motivador para o estudo da codificação de rede em primeiro lugar.

A programação puramente funcional é uma abstração popular que oferece, pelo menos de acordo com seus proponentes, um grande aumento no poder expressivo do código, entre outros benefícios. No entanto, como é um modelo restritivo da máquina - em particular, não permite memória mutável -, levanta a questão da desaceleração assintótica em comparação com o modelo usual (RAM).

Há uma grande discussão sobre esta questão aqui . Os principais tópicos parecem ser:

1. Você pode simular memória mutável com uma árvore binária balanceada; portanto, o pior dos casos é o O (log n).
2. Com uma avaliação ansiosa , há problemas para os quais você pode fazer o melhor.
3. Na avaliação preguiçosa , não se sabe se existe ou não uma lacuna. No entanto, existem muitos problemas naturais para os quais nenhum algoritmo puramente funcional conhecido corresponde à complexidade ideal da RAM.

Parece-me que essa é uma pergunta surpreendentemente básica a ser aberta.

Enquanto sua pergunta se concentra na teoria da complexidade, coisas semelhantes podem acontecer em outros campos, como a teoria das linguagens de programação. Aqui estão alguns exemplos em que a abstração torna algo indecidível (ou seja, o limite inferior no modelo fraco é impossível, enquanto o modelo forte permite que o algoritmo seja expresso):

• No cálculo lambda, existem funções que você não pode expressar diretamente (ou seja, como um termo lambda que reduz beta para o resultado desejado). Um exemplo é paralelo ou (uma função de dois argumentos que retornam o que termina). Outro exemplo é uma função que imprime seu argumento literalmente (uma função obviamente não pode distinguir entre dois argumentos beta-equivalentes). A falta de expressividade deve-se à imposição da abstração de que termos lambda equivalentes a beta devem ser tratados de forma idêntica.

• Em uma linguagem de tipo estaticamente que possui apenas polimorfismo paramétrico , como o ML sem nenhuma extensão sofisticada, é impossível escrever algumas funções - você obtém teoremas gratuitamente . Por exemplo, uma função cujo tipo é (seja qual for o tipo do argumento, retorne um objeto do mesmo tipo) deve ser a função de identidade ou não-finalizadora. A falta de expressividade se deve à abstração de que, se você não conhece o tipo de um valor, é opaco (você só pode repassar).$\forall\alpha, \alpha\to\alpha$

O "preço da abstração" também pode ser encontrado ao resolver o problema do logaritmo discreto na criptografia. Shoup (1997) mostrou que qualquer abordagem genérica (ou seja, algoritmos que usam apenas operações de grupo) deve usar pelo menos operações do grupo, ondemé o tamanho do grupo. Isso corresponde à complexidade doataque de aniversáriogenérico. Entretanto, algoritmos como ocálculo Indexou oalgoritmo Pohlig-Hellmanconfiam na estrutura teórica dos números de Z ∗ n para obter algoritmos um pouco mais rápidos (pelo menos em grupos de ordem suave).$\Omega(\sqrt{m})$$m$$\mathbb{Z}_n^*$

Essa observação é uma das razões para a popularidade da criptografia de curva elíptica (em oposição à criptografia em grupos como ), pois, essencialmente, só conhecemos abordagens genéricas para resolver o problema do logaritmo discreto em grupos baseados em curvas elípticas.$\mathbb{Z}_n^*$

Aqui está um exemplo de algoritmos de gráfico. Dado um grafo orientado com pesos não-negativos sobre as bordas, as todos os pares de gargalo caminhos problema é o de calcular, para todos os pares de vértices e t , o fluxo máximo que pode ser empurrado ao longo de algum caminho de s a t . (Formalmente, estamos apenas maximizando o peso mínimo de uma aresta em qualquer caminho de s para t . Mais formalmente, estamos substituindo min e + na definição de caminhos mais curtos de todos os pares por max e min .)$s$$t$$s$$t$$s$$t$$\min$$+$$\max$$\min$

Seja o número de vértices no gráfico de entrada. Sabe-se que esse problema requer Ω ( n 3 ) tempo no modelo de comparação de caminhos de Karger, Koller e Phillips , assim como o problema de caminhos mais curtos de todos os pares exige . (O modelo de caminho-de comparação suporta os algoritmos tradicionais, tais como Floyd-Warshall.) No entanto, ao contrário de todos os pares de caminhos mais curtos, verifica-se que todos os pares de gargalo caminhos podem ser resolvidos em menos do que S ( n 2,8 ) tempo utilizando a multiplicação de matrizes rápido .$n$$\Omega(n^3)$$O(n^{2.8})$

Por uma discussão nesta questão , muitos problemas em geometria computacional têm limites inferiores na árvore de decisão algébrica ou nos modelos de árvore de computação algébrica, decorrentes de problemas fundamentais como classificação ou distinção de elementos . Não é difícil encontrar documentos alegando que os limites superiores de O ( n log n ) em problemas relacionados, como a construção de triangulações de Delaunay, são ótimos, porque correspondem a esses limites inferiores.$\Omega(n\log n)$$O(n\log n)$

Porém, quando a entrada é especificada em coordenadas cartesianas inteiras (como costuma ser na prática, o ponto flutuante é um ajuste inadequado para a geometria computacional), esses limites inferiores não correspondem ao modelo computacional. Talvez não seja surpreendente que problemas do tipo de busca por faixa ortogonal possam ser resolvidos mais rapidamente usando técnicas adaptadas da classificação inteira, mas mesmo problemas não ortogonais podem frequentemente ter algoritmos mais rápidos (que resolvem o problema exatamente, em modelos de computação que permitem aritmética inteira com O (1). ) vezes a precisão dos números inteiros de entrada). Veja, por exemplo, arXiv: 1010.1948 para um conjunto de exemplos.

Existem muitos exemplos desse tipo em criptografia, especialmente provas de zero conhecimento. Veja, por exemplo, a tese:

Boaz Barak, Técnicas Não-Caixa-Preta em Criptografia, 2003.

(Aliás, o título da tese fornece uma prova de zero conhecimento da validade deste comentário :)

$\Omega(n \log n)$$\Omega(n \log n)$$O(n)$algoritmo de tempo esperado para resolver o par mais próximo de pontos no plano, que é uma generalização da exclusividade do elemento. Ele escapa da Árvore de Decisão Algébrica vinculada usando o hash. Encontrei-o no livro Algorithm Design, de Klein e Tardos. Existe um algoritmo semelhante, porém mais complicado, para solucionar o mesmo problema descrito no blog de RJ Lipton .

Referência:

• Richard J. Lipton, " Rabin lança uma moeda ", março de 2009
  publicado no Lost Letter de Godel e no blog P = NP .

$k$$3$$k$$3$

$k$$\Omega(k)$

No entanto, essa abstração é indiscutivelmente errada: se você puder transmitir algo em uma rede de comunicação, terá alguma maneira de codificar "algo" como uma sequência de bits. E agora as coisas começam a parecer muito melhores.

$1, 2, ..., k$$O(\log^* k)$$1, 2, ..., 10^{10^k}$$O(\log^* k)$

$O(\log^* k)$$\Omega(k)$

Um exemplo que me vem à mente é o cálculo do volume. Um resultado de Barany e Furedi é que você precisa de um número exponencial de consultas e existe um algoritmo de tempo polinomial aleatório de Dyer-Frieze-Kannan . A diferença representa o prêmio da abstração e também o benefício da aleatoriedade, mas acho que a principal razão para a diferença é o preço da abstração. (Espero ter entendido a pergunta e ela vai na direção certa.)

Provavelmente, isso não é exatamente o que você tinha em mente. Mas, em certo sentido, a independência de P vs NP dos oráculos é um exemplo. O que realmente diz é que, se você se importa apenas com simulação e enumeração (por exemplo, se esse é o seu "modelo" de computação), não é possível separar essas classes ou reduzi-las.

Um exemplo algorítmico mais concreto vem da pesquisa aproximada de faixa na direção "reversa". Especificamente, a maioria dos problemas de pesquisa de intervalo é redigida como somas de semigrupos, e os limites inferior / superior são expressos sem levar em consideração a estrutura desse semigrupo (exceto algumas condições técnicas leves). Trabalhos recentes de Arya, Malamatos e Mount mostram que, se você observar atentamente a estrutura do semigrupo (as propriedades de idempotência e integralidade), poderá provar limites diferentes (e mais rígidos) para a pesquisa aproximada de alcance.

O teorema da amostragem de Shannon-Nyquist propõe uma condição suficiente para os limites teóricos da informação na comunicação. A teoria da amostragem é trabalhada em torno de exemplos em que o sinal recebido tem uma representação compacta / aleatória. Avanços recentes na amostragem mostram que essa abstração talvez acarrete um preço - que o tipo de coisa que estamos interessados ​​em medir geralmente tem representações esparsas, de modo que esses limites não sejam rígidos. Além disso, as informações podem ser codificadas de uma maneira muito mais densa do que se pensava originalmente.

• Os códigos de correção de erros sugerem que alguma reavaliação do limite de Shannon em ambientes de rede sujeitos a ruído.
• O novo campo do sensor de compressão empurra a reconstrução das variedades de imagens que encontramos de maneira interessante além do limite de Shannon.

Muitos problemas interessantes que as ciências da natureza apresentam acabam sendo difíceis de lidar com PN no sentido clássico. Embora essa noção seja teoricamente perfeitamente válida, ela não ajuda o biólogo ou físico de forma alguma. Descobrimos que alguns problemas difíceis de NP são tratáveis ​​com parâmetros fixos e, muitas vezes, com um parâmetro que é observado como limitado por uma pequena constante no mundo real.

Ou seja, o TCS nos diz que não esperamos uma solução eficiente para o problema abstrato, mas podemos resolver instâncias que ocorrem de fato rapidamente - uma lacuna.

Neste artigo, http://www.mimuw.edu.pl/~szymtor/papers/atom-turing.pdf , estudamos as máquinas de Turing que têm acesso limitado aos dados. Isso é formalizado como invariável sob automorfismos de uma estrutura relacional; por exemplo, no limite inferior de O (n log n) para classificação, você diria que a máquina pode processar e armazenar números racionais, mas suas transições devem ser invariantes sob automorfismos de (Q, <), ou seja, bijeções monótonas. A definição formal é mais complicada, a fim de especificar com precisão que tipo de estrutura de dados a máquina pode armazenar em sua memória (ela deve ser "finita"
em algum sentido, mas permitimos armazenar estruturas mais complicadas do que apenas as tuplas de valores de dados, como tuplas não ordenadas).

No artigo, provamos alguns limites inferiores para outras máquinas de Turing com "acesso restrito a dados". Em particular, mostramos que:

• Uma máquina de Turing determinística que pode manipular vetores (digamos sobre o campo de dois elementos), mas só pode usar testes de adição e igualdade de vetores, não pode determinar em tempo polinomial se uma determinada lista de vetores é linearmente dependente (formalmente, as transições das máquinas devem invariante sob automorfismos do espaço vetorial). Isso se opõe às máquinas não determinísticas, que podem simplesmente adivinhar uma combinação dos vetores que chega a 0. Observe que a eliminação gaussiana ocorre em tempo polinomial, mas tem acesso às coordenadas dos vetores; em particular, suas transições não são invariantes sob automorfismos do espaço vetorial.

• Em um modelo definido adequadamente, as Máquinas de Turing que podem comparar números naturais apenas em relação à igualdade (nem mesmo <) não podem ser determinadas. Aqui, consideramos a estrutura relacional (N, =) e as máquinas que são invariantes sob seus automorfismos. Existe uma construção (semelhante à construção de Cai-Furer-Immerman da Teoria dos Modelos Finitos) que mostra que, de fato, neste modelo P ≠ NP. Permitir que as máquinas comparem os números usando <lhes fornece energia suficiente para determinar.

Um preço geral da abstração está presente em estruturas de caixa preta, como a complexidade da árvore de decisão ou a complexidade da consulta quântica. Se restringimos a análise a esses modelos, geralmente podemos encontrar limites muito bons na complexidade das tarefas. De fato, para consultas quânticas, podemos basicamente resolver a complexidade dos problemas porque o método adversário negativo fornece limites mais baixos (dentro de um fator de log n / loglog n: 1005.1601 ). Isso nos fornece uma ótima ferramenta para analisar a complexidade da consulta, mas muitas vezes fica difícil comparar a complexidade da consulta com uma complexidade mais padrão de tempo / espaço da máquina de turing (exceto como um limite inferior bruto).

Aqui estão dois exemplos, ambos relacionados a modelos contínuos versus modelos discretos:

1. $[0,1]$$x$$y$$x<y$$x=y$$x>y$$x$$|x-y|$$y=x$

   $y$$[0,1]$$y=x$

2. A motivação para o problema A vem do problema da divisão de bolos sem inveja . Stromquist mostrou que nenhum protocolo finito (mesmo que ilimitado) pode garantir uma divisão livre de inveja de um bolo entre três ou mais jogadores, se cada jogador receber uma única peça conectada.

   $i$$\alpha$$i$$x$$vi(0,x) = \alpha$

   Além disso, o resultado não está relacionado a algoritmos com operações contínuas, como procedimentos com facas em movimento.

Quando expressa na lógica de primeira ordem, qualquer prova do princípio do buraco de pombo para n fixo é de comprimento exponencial. No entanto, com aritmética, a prova pode ser expressa de forma muito mais concisa.

O sucesso dos solucionadores SMT veio do recuo do modelo abstrato de redução de problemas para o SAT, permitindo que teorias mais ricas reduzam bastante a quantidade de cálculos necessários.