Exemplos do preço da abstração?

112

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

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.

Joshua Grochow
fonte
3
Eu realmente gosto desta pergunta; ansioso para ver mais respostas.
randomwalker
11
Há também um custo "implícito" de abstração. Você menciona o exemplo do preço da abstração na classificação e como esses resultados abstraídos não se aplicam aos números de classificação (o que pode de fato ser feito mesmo em O (n) com bucketsort em alguns casos). Os limites inferiores nos diagramas de Voronoi geralmente são derivados, mostrando que há uma redução linear do tempo de um diagrama de Voronoi para a classificação de uma lista de números. E muitos algoritmos geométricos derivam limites inferiores desse limite inferior na computação dos voronoi.
Ross Snider
por que este é um wiki da comunidade?
Nanda
11
@nanda: Porque não existe uma resposta certa e, de fato, a pergunta foi projetada para gerar muitas respostas certas, como eu acho.
Joshua Grochow 01/09/10
11
Parece que você pode realmente estar se referindo ao relaxamento em vez de abstração
vzn

Respostas:

38

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.

Suresh Venkat
fonte
33

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.

randomwalker
fonte
dado que a programação funcional é um modelo para grandes cálculos de dados (consulte MapReduce), essa desaceleração é potencialmente bastante significativa.
Suresh Venkat
5
Além disso, é importante ter em mente que as advertências mencionadas no encadeamento SO. Ou seja, o limite inferior de um problema está em um modelo ainda mais restrito: on-line com elementos atômicos. Eu acredito que um limite inferior dessa forma no modelo padrão de programação funcional ainda está aberto. Ω(nlogn)
Joshua Grochow
11
Pelo menos, o artigo mencionado nesse tópico ([Bird, Jones e De Moor, 1997], veja a referência completa) estabelece uma lacuna entre a avaliação ansiosa e preguiçosa.
Blaisorblade 10/09/10
Para cálculos de dados muito grandes, o custo de IO deve dominar com tanta força que a desaceleração logarítmica nos cálculos não deve importar, certo?
Adriann
O que você quer dizer com ordem de avaliação?
libeako 16/09
28

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).α,αα

Gilles
fonte
4
Gostaria de poder votar novamente várias vezes.
Jacques Carette
26

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).Ω(m)mZn

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

MRA
fonte
25

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 .)stststmin+maxmin

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Ω(n3)O(n2.8)

Ryan Williams
fonte
22

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.Ω(nregistron)O(nregistron)

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.

David Eppstein
fonte
Obrigado por destacar o "paradoxo" e o recente artigo de Chan e Pǎtraşcu.
András Salamon
17

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 :)

Piotr
fonte
Corrija o ano de citação, de 2006 a 2003.
MS Dousti
@Sadeq Dousti: pronto. É wiki comunidade e você tem mais reputação do que eu, então eu acho que você poderia ter corrigido isso sozinho ;-)
Blaisorblade
17

Ω(nregistron)Ω(nregistron)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:

Kaveh
fonte
15

k3k3

kΩ(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 1,2,...,kO(registrok)1 1,2,...,1010kO(registrok)

O(registrok)Ω(k)

Jukka Suomela
fonte
13

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

Gil Kalai
fonte
10

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.

Suresh Venkat
fonte
4
XPXNPXPNPPX=NPXNP=coNP. O trabalho deles é um tanto polêmico (acho que se trata de relativizar classes limitadas por espaços pequenos), mas acho muito interessante.
Joshua Grochow
10

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.
Ross Snider
fonte
Você pode dar algumas referências para isso :)?
Vivek Bagaria
8

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.

Rafael
fonte
5

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.

Szymon Toruńczyk
fonte
2

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

Artem Kaznatcheev
fonte
Você tem alguns exemplos específicos de onde isso mostrou um limite inferior que pode ser quebrado ao "abrir a caixa preta"?
Joshua Grochow 22/10/10
a classificação de poços é um exemplo em que o modelo da árvore de decisão fornece n log n, mas você pode melhorar observando a estrutura da entrada.
Suresh Venkat
@ Suresh: eu quis dizer exemplos que ainda não foram mencionados :).
21710 Joshua Grochow
Desculpe, minha culpa.
Suresh Venkat
Bem, às vezes você pode ter uma complexidade quântica de consulta relativamente agradável, mas nenhum algoritmo de execução rápida. Um exemplo é o problema do subgrupo oculto, em que precisamos de um número polinomial de consultas, mas ainda um tempo exponencial (embora obviamente o limite inferior do tempo não seja comprovado) para qualquer algoritmo conhecido [1]. Este é um preço na direção oposta, eu acho. [1] arxiv.org/abs/quant-ph/0401083
Artem Kaznatcheev
1

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

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

    y[0 0,1 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.

    EuαEuxvEu(0 0,x)=α

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

Erel Segal Halevi
fonte
0

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.

Arthur B
fonte