Existem mais problemas de tempo polinomial com limites mais baixos de complexidade?

Estou procurando mais problemas em com limites mais baixos de complexidade de tempo clássica. Algumas pessoas podem se perguntar como você pode provar um limite tão baixo. Ver abaixo.$P$

Limites inferiores exponenciais:

Reivindicação: Se você tiver um problema que é E X P T I M E completo com reduções polinomiais, existe uma constante α ∈ R tal que X não pode ser solucionado no tempo O ( 2 n α ) . $X$$EXPTIME$$\alpha \in \mathbb{R}$$X$$O(2^{n^{\alpha}})$

Ideia de prova: pelo teorema da hierarquia de tempo, há um problema no tempo de O ( 2 n ) que não está em o ( 2 $Y$$O(2^n)$tempo. Além disso, deve haver uma redução polinomial deYparaX. Portanto, existe uma constantecde tal forma que essa redução leva um exemplo de tamanhonparaYa uma instância de tamanhoncparaX. O limite inferior paraYdeO(2n 1 - ϵ )muda para um limite inferior paraXdeO(2n 1 - $o(\frac{2^n}{n})$$Y$$X$$c$$n$$Y$$n^c$$X$$Y$$O(2^{n^{1-\epsilon}})$$X$tempo.$O(2^{n^{\frac{1-\epsilon}{c}}})$

Limites inferiores polinomiais:

Alguns problemas -Complete têm nice parametrizações em problemas de tempo polinomial. Considere o problema X de antes. Suponha que tenhamos uma parametrização k - X para X tal que:$EXPTIME$$X$$k$$X$$X$

• Para cada fixo , k - X está no tempo polinomial.$k$$k$$X$

É claro que há exceções nisso, mas intuitivamente, à medida que o cresce, os problemas do k - X devem ficar mais difíceis porque X tem um limite inferior da complexidade de tempo exponencial.$k$$k$$X$$X$

Um exemplo:

Um exemplo de problema que surgiu é o não vazio de interseção para autômatos em árvore. Ou seja, dada uma lista finita de autômatos de árvores, existe uma árvore que satisfaça simultaneamente todos os autômatos?

$EXPTIME$$k$$k$$n^{\Theta(k)}$

Questão:

$EXPTIME$

Aqui está um que envolve um jogo de pedras para 2 jogadores. Você decide se é natural (:

T. Kasai, A. Adachi, S. Iwata. Classes de jogos de calhau e problemas completos. 1979

O teorema 3.1 tem a EXPTIME-completude de seixos. O teorema 3.3 tem a facilidade do k-seixo.

A. Adachi, S. Iwata, T. Kasai. Alguns problemas combinatórios de jogos exigem tempo Omega (n ^ k). 1984

O teorema 3.2 tem o limite inferior no k-seixo. Por fim, você também pode estar interessado em:

T. Kasai e S. Iwata. Problemas gradualmente intratáveis ​​e limites inferiores não-determinísticos do espaço de log. 1985

Infelizmente, estes estão todos por trás de paywalls :(