Estou procurando exemplos de problemas para os quais é fácil obter algoritmos em execução no tempo ou 2 O ( n c ) para alguns c > 1, mas para os quais não se sabe se existe um algoritmo em execução no tempo 2 O ( n ) .
Estou interessado principalmente em problemas teóricos dos grafos, mas outros bons exemplos também seriam bem-vindos.
Por exemplo, é trivial desenvolver um algoritmo executando no tempo para o problema do caminho hamiltoniano. Apenas teste todas as permutações. Usando programação dinâmica, no entanto, é possível atingir o tempo 2 O ( n ) . Existem outros problemas de conectividade natural ou variações do problema do caminho hamiltoniano para os quais nenhum algoritmo em execução no tempo 2 O ( n ) é conhecido?
fonte
Isomorfismo Permutacional de Grupos de Permutação, também conhecido como Conjugação de Grupos de Permutação:
(onde significa o subgrupo gerado pelo π i ).⟨ ¸1, … , Πk⟩ πEu
Como no exemplo do caminho hamiltoniano, existe um trivial ! = 2 O ( n log n ) algoritmo. O mais conhecido atualmenten ! = 2O ( n logn ) é onde L = ⟨ π 1 , ... , π k ⟩ . Note que | G | pode ser tão grande quanto n ! (trivialmente: G = S n2O ( n )| G |O ( 1 ) L = ⟨ ¸1, … , Πk⟩ | G | n ! G = Sn ) ou até para G não trivial (consulte, por exemplo, o Teorema de O'Nan-Scott ). * Removendo a dependência de | G | foi deixado lá como um importante problema em aberto.n ! / nO ( 1 ) G | G |
* - Apesar de ser grande, portanto, na pior das hipóteses, isso parece assintoticamente não melhor que trivial, acontece que 2 O ( n ) | G | O ( 1 ) foi exatamente o necessário para o teste de isomorfismo no tempo polinomial de grupos sem subgrupos normais abelianos.G 2O ( n )| G |O ( 1 )
fonte
Calculando o número de cruzamento de um gráfico. Os algoritmos exatos existentes envolvem a formulação como um programa linear inteiro com um número de variáveis cúbicas no número de arestas [Chimani et al, ESA 2008] . Mesmo para o número restrito de cruzamento de uma página, no qual os vértices são colocados no limite de um disco e nas bordas internas do disco, algoritmos conhecidos são exponenciais em vez de exponenciais individuais [Bannister et al. GD 2013] .O ( n logn )
fonte