sequência de problemas que levam

Conhecemos uma sequência infinita de problemas de decisão em que o algoritmo mais eficiente para cada problema ocorre $\Theta(n^k)$ hora, onde $k$ aumenta sem limites?

Suponha, por exemplo, que saberíamos que encontrar um k-clique requer $\Theta(n^k)$, essa sequência pode ser {1-clique, 2-clique, 3-clique, ...}. No entanto, talvez haja algoritmos mais eficientes para o k-clique, portanto esta resposta está incorreta.

EDITAR:

• Pelo Teorema da Hierarquia de Tempo (que inclui "P não diminui para DTIME ($n^k$) para qualquer fixo $k$"), essa sequência deve existir.
• Após algumas discussões nos comentários, problemas comuns de PN não são bons candidatos. Se demorar apenas$O(n)$ hora de verificar um certificado (ou $O(n^c)$, Onde $c$ é uma constante independente de $k$), implicaria que $P\neq NP$

Você deixa o modelo computacional aberto. Assumirei que a pergunta se refere a máquinas de acesso aleatório (RAMs), como é habitual quando se pede o expoente real no tempo polinomial.

Deixei $P_k$ ser o conjunto de (codificações de) RAMs $M$, de tal modo que $M$ pára no máximo $|M|^k$ etapas usando no máximo a inicial $|M|^k$células de memória. Uma RAM universal pode resolver$P_k$ no $O(n^k)$.

Por outro lado, $P_k$ é o problema universal para $DTIME(n^k)$(no modelo de RAM e com reduções lineares de tempo). Como um caso especial da versão RAM do teorema da hierarquia de tempo, uma simples diagonalização mostra que todos os algoritmos para$P_k$ tem tempo de execução $\Omega(n^k)$. Assim, a complexidade de$P_k$ é $\Theta(n^k)$ como solicitado.

O aperto depende fortemente do modelo computacional. A versão da máquina de Turing do teorema da hierarquia de tempo tem um$\log n$Gap = Vão. Deixei$P'_k$ ser o conjunto de (codificações de) máquinas de Turing $M$, de tal modo que $M$ pára no máximo $\frac{|M|^k}{\log n}$passos. Então$P'_k$ pode ser resolvido em $n^k$ tempo por uma máquina universal de Turing e todos os algoritmos têm tempo de execução $\Omega(\frac{n^k}{\log n})$. Eu suspeito que este é o melhor que se pode fazer.

[EDITAR]

Em um comentário, você pede mais convencional problemas , como problemas de gráficos ou lógica.

Primeiro, deixe-me mostrar como $k$-Clique (como sugerido na resposta) não parece ser um bom candidato. Se pudéssemos provar isso$k$-Clique requer tempo $\Omega(n^k)$ (ou $\Omega(n^{f(k)})$ para alguns ilimitados $f$), sugerimos que o Clique não está em P. E, portanto, P é diferente de NP. Não é provável que seja fácil. O mesmo vale para fatias de qualquer outro problema que sabemos estar no NP ou em algumas outras classes, como PSPACE, desconhecidas por serem diferentes de P.

Todo problema pode ser reformulado como um problema gráfico, codificando a entrada como um gráfico. Não sei se você chamaria uma versão gráfica de$P_k$convencional. Eu não chamaria isso de natural.

Quanto à lógica, posso fornecer um exemplo. No entanto, não é uma lógica booleana e existe uma lacuna entre o limite inferior e o superior. O exemplo é baseado no teorema de Immerman-Vardi. Deixei$\mathcal L$ser lógica de primeira ordem estendida por operadores de ponto menos fixo. Deixei${\mathcal L}^k$ denotar o fragmento onde apenas $k$variáveis ​​de primeira ordem são permitidas. É permitido reutilizar variáveis, portanto a restrição é que cada sub-fórmula tenha no máximo$k$variáveis ​​livres. O problema$M_k$ é o problema de verificação de modelo para ${\mathcal L}^k$, que está na entrada de uma fórmula $\varphi\in{\mathcal L}^k$ e uma estrutura $\mathfrak A$ do vocabulário correspondente, a tarefa é decidir se $\mathfrak A\models\varphi$, é se $\varphi$ é verdade em $\mathfrak A$.

$M_k$ pode ser resolvido a tempo $O(n^{2k+1})$. Por outro lado, por algumas constantes$c$, $M_{3k+c}$ é difícil para $DTIME(n^k)$ (onde também exigimos um $n^k$ligado ao conteúdo das células da memória). Acredito$c=2$é suficiente. A partir da diagonalização, obtemos que$M_{3k+c}$ requer tempo $\Omega(n^k)$, tão $M_k$ requer tempo $\Omega(n^{\frac{k-c}3})$. O limite não é apertado no sentido de$\Theta(n^{k'})$ para alguns $k'$, mas pelo menos temos $n^{\Theta(k)}$.