Algoritmos de tempo polinomial com enorme expoente / constante

59

Você conhece algoritmos sensíveis que são executados em tempo polinomial em (Comprimento de entrada + Comprimento de saída), mas cujo tempo de execução assintótico na mesma medida tem um expoente / constante realmente grande (pelo menos, onde o limite superior comprovado no tempo de execução é dessa maneira)?

Joris
fonte
3
Veja mathoverflow.net/questions/65412 : "O pior algoritmo conhecido em termos de big-O ou mais precisamente big-Theta". Eu postei uma resposta lá.
Joseph O'Rourke
4
Há algoritmo LOGSPACE do Reingold para conectividade (veja uma pergunta sobre sua complexidade de tempo ), mas duvido que seja sensível no sentido você quer dizer aqui ...
Janne Korhonen H.
1
@ Joseph ORourke: Eu tenho o papel "retângulo gordo" em minha mesa agora!
Aaron Sterling
3
Embora o n42. fosse um cálculo legítimo (a programação dinâmica aumenta), eu o incluí na versão da conferência como uma piada , uma piada removida na versão do diário.
Joseph O'Rourke
9
O reconhecimento de gráficos perfeitos está em O(|V(G)|9) , e uma inovação parece ser necessária para melhorar isso.
András Salamon

Respostas:

39

Algoritmos baseados no lema da regularidade são bons exemplos para algoritmos de tempo polinomial com constantes terríveis (no expoente ou como coeficientes iniciais).

O lema de regularidade de Szemeredi diz que em qualquer gráfico em vértices você pode particionar os vértices em conjuntos onde as arestas entre pares de conjuntos são "pseudo-aleatórias" (ou seja, densidades de subconjuntos suficientemente grandes se parecem com densidades em um gráfico aleatório) . Essa é uma estrutura muito agradável de se trabalhar e, como conseqüência, existem algoritmos que usam a partição. O problema é que o número de conjuntos na partição é uma torre exponencial no parâmetro de pseudo-aleatoriedade (veja aqui: http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemman ).

Para alguns links para algoritmos que dependem do lema da regularidade, consulte, por exemplo: http://www.cs.cmu.edu/~ryanw/regularity-journ.pdf

Dana Moshkovitz
fonte
2
Bom ponto! No entanto, não estou ciente de um problema computacional em que exista um limite inferior correspondente da torre de exponenciais. Gowers provou ser um limite tão baixo para o próprio lema da regularidade, mas não conheço um problema computacional em que ele se aplique.
Arnab #
3
Acredito que os algoritmos de agrupamento descritos por Chazelle neste artigo ( arxiv.org/abs/0905.4241 ) tenham uma convergência ótima (isto é, com limites mais baixos) que é uma torre de dois
Suresh Venkat
Em um artigo recente ( eccc.hpi-web.de/report/2014/018 ), mostro alguns outros algoritmos usando o lema de regularidade (aritmética) que têm constantes enormes ocultas pela notação O ().
arnab
55

Notícias da SODA 2013 : O problema da bissecção máxima é aproximado a um fator 0,8776 em torno de .O(n10100)

Jagadish
fonte
54

Aqui estão duas capturas de tela de Uma abordagem orientada a energia para o desdobramento de ligações por Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O'Brien, SOCG 2004:

Corolário 1. O número de etapas em nosso algoritmo é no máximo $ 1752484608000 n ^ {79} L ^ {25} / D ^ {26} (\ Theta_0) $

Corolário 2. O número de etapas em nosso algoritmo é no máximo $ 117607251220365312000 n ^ {79} (\ ell _ {\ max} / d _ {\ min} (\ Theta_0)) ^ {26} $]

Jeffε
fonte
12
A constante é muito mais impressionante do que o poder de :)n
Suresh Venkat
11
Este é um algoritmo com enorme expoente E enorme constante ...
Hsien-Chih Chang #: 27411
5
Os mesmos limites são válidos para o Bubblesort.
Raphael
1
Quão apertados são esses limites?
Max
34

Aqui está um resultado recente dos quebra-cabeças pendurados em papel da FUN 2012 de Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph SB Mitchell, Ronald L. Rivest e Mihai Patrascu.

Mostramos como pendurar uma imagem enrolando uma corda em torno de n unhas, fazendo um número polinomial de torções, de modo que a imagem caia sempre que qualquer k das n unhas é removido, e a imagem permanece suspensa quando menos de k unhas são removidas.

Não deixe o 'número polinomial' enganá-lo ... ele é .O(n43737)

Jagadish
fonte
15
Isso é (!!)(618)#gates em uma rede de classificação da AKS
Jeffε
23

Existe uma classe de problemas cujas soluções são difíceis de calcular, mas é fácil aproximar delas com precisão , no sentido de que existem algoritmos de tempo polinomial que podem aproximar a solução dentro de para qualquer constante ε> 0. No entanto, há um problema: o tempo de execução dos aproximadores pode depender muito de 1 / ϵ , por exemplo, ser O ( n 1 / ϵ )(1+ϵ)1/ϵO(n1/ϵ) .

Veja mais informações aqui: http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme .

Sadeq Dousti
fonte
17

Embora o tempo de execução de tais algoritmos tenha sido subsequentemente aprimorado, o algoritmo original para amostragem de um ponto de um corpo convexo teve tempo de execução O~(n19) .

Dyer, Frieze e Kannan: http://portal.acm.org/citation.cfm?id=102783

Aaron Roth
fonte
16

Se é uma lógica modal ou superintuicionista tabular, os sistemas estendidos de prova de Frege e de substituição de Frege por L são polinomialmente equivalentes e polinomialmente fielmente interpretáveis ​​na EF clássica (este é o Teorema 5.10 neste artigo ). O expoente c das simulações polinomiais não é explicitamente declarado no Teorema 5.10, mas a prova indutiva do teorema fornece c = 2 O ( | F | ) , onde F é uma estrutura finita de Kripke que gera L , portanto pode ser tão grande como você deseja, dependendo da lógica. (Fica pior no Teorema 5.20.)eueucc=2O(|F|)Feu

Emil Jeřábek
fonte
16

O atual algoritmo mais conhecido para reconhecer gráficos de mapas (uma generalização de gráficos planares) é executado em . Thorup, gráficos de mapa em tempo polinomial.n120

A computação do equilíbrio do mercado de Arrow-Debreu utiliza cálculos de fluxo máximo de , onde U é a utilidade máxima. Duan, Mehlhorn, um algoritmo polinomial combinatório para o mercado de seta linear-Debreu.O(n6log(nU))você

adrianN
fonte
Eu recebo um erro do IEEE quando sigo o seu link, mas presumo que você esteja se referindo ao documento FOCS'98 de Thorup, "Mapeie gráficos em tempo polinomial".
18712 David Eppstein
1
Quero dizer esse papel, e ele carrega bem para mim.
Adriann
trabalha para mim a partir dos EUA.
Suresh Venkat
12

Problema de transitoriedade da pilha de areia

Considere o seguinte processo. Pegue um ladrilho grosso e jogue partículas de areia nele, um grão de cada vez. Um monte se acumula gradualmente e, em seguida, uma grande parte da areia desliza pelas bordas do ladrilho. Se continuarmos a adicionar partículas de areia, depois de um certo tempo, a configuração do heap será repetida. Posteriormente, a configuração se torna recorrente, ou seja, continua revisitando um estado que é visto anteriormente.

Considere o seguinte modelo para o processo acima. Modelar o azulejo como um grid. Partículas de areia são jogadas nos vértices dessa grade. Se o número de partículas em um vértice exceder seu grau, o vértice entra em colapso e as partículas nele se movem para vértices adjacentes (em cascata). Uma partícula de areia que atinge um vértice limite desaparece em uma pia ("cai"). Isso é conhecido como Modelo Abeliano de Pilha de Areia .n×n

Problema: Quanto tempo leva para a configuração se tornar recorrente em termos de , assumindo o pior algoritmo para a queda de partículas de areia?n

Em SODA '07 , László Babai e Igor Gorodezky provaram que desta vez eram polinomialmente limitados, mas ..

insira a descrição da imagem aqui

No SODA '12 , Ayush Choure e Sundar Vishwanathan melhoraram esse limite para .O(n7)

Esta resposta teria ficado um pouco melhor se não fosse pela melhoria deles :)

Jagadish
fonte
11

O problema do "crânio convexo" é encontrar o polígono convexo da área máxima dentro de um determinado polígono simples. O algoritmo mais rápido conhecido por esse problema é executado no tempo [Chang e Yap, DCG 1986].O(n7)

Jeffε
fonte
10

A solução dos Jogos de Aniquilação (Fraenkel e Yesha) tem complexidade .O(n6)

Yuval Filmus
fonte
6

O(n11)

Lamine
fonte
-3

O(2n)n(n1)(n2)(n3)O(nc)c(nc)cPNP ou algo mais forte.

[1] Perguntas sobre o cálculo da rigidez da matriz

vzn
fonte
2
Não tenho certeza de como isso é diferente (por exemplo) de tentar encontrar um clique máximo, enumerando todos os conjuntos de tamanho k, para aumentar k. cada etapa também é p-time para k fixo.
Suresh Venkat
sim, é muito semelhante e me lembra a conjectura de isomorfismo Hartmanis para conjuntos NP. mesmo que a conjectura do isomorfismo não seja verdadeira (o consenso atual / a sabedoria convencional parece inclinar-se contra ela), parece que os conjuntos de PN têm alguma propriedade semelhante, mas talvez um pouco mais fraca, o que também parece exigir uma pesquisa exaustiva
vzn
-4

cO(nc)(nc)PNP

vzn
fonte
2
1. existe um algoritmo (simples) que melhora um pouco o expoente. 2. esta é uma afirmação muito mais forte que P não é igual a NP, assim como ETH é mais forte que P não é igual a NP. Penso que algoritmos como este não foram apontados porque parece que o OP não está interessado em tipos exaustivos de algoritmos de pesquisa.
Sasho Nikolov
5
cncO(c)
5
k>2 k2sknsk>0
6
k2knkk2O(k)n
5
2O(n)2O(n)