Se o limite inferior de um problema é exponencial, então é NP?

Supondo que temos um problema e mostramos que o limite inferior para resolver é . $p$ $p$ $\mathcal{\Omega}(2^n)$

O limite inferior implica o problema no ? $\mathcal{\Omega}(2^n)$ $NP$

time-complexity np-complete kelalaka
fonte

Não é NP, mas é NP-difícil.

user35734

Como você sabe que é NP-difícil?

Yuval Filmus

Se você pudesse mostrar um problema tanto em quanto em NP, teria provado P NP.

Ω (2^{n})

$\mathcal{\Omega}(2^n)$

\neq

$\neq$

kasperd

@kasperd: Chamamos isso de Quebra-cabeças de Merkle, mas deve ser excluído de P =? NP porque o formulário específico não produz outros com as mesmas propriedades e uma prova de P = NP provavelmente elimina qualquer maneira de fazer os quebra-cabeças de Merkle que realmente funcionam como pretendido. O tempo exponencial de Merkle's Puzzles também é PSPACE para o usuário pretendido.

Joshua

Os quebra-cabeças de @Joshua Merkle não são exponenciais na dependência do tamanho da entrada . (Bem, se assumirmos que a solução para Alice é polinomial).

rus9384

Respostas:

Não. Por exemplo, o problema de parada tem um limite inferior , mas não está no NP (pois não é computável). $\Omega(2^n)$

O teorema da hierarquia de tempo não determinístico mostra que qualquer problema completo de NEXP é outro exemplo (com potencialmente substituído por uma função exponencial menor ). $2^n$ $c^{n^\epsilon}$

NP é um limite superior para a complexidade de um problema.

Yuval Filmus
fonte

Você poderia dar um exemplo de um problema que é mas não é NP-difícil?

Ω (2^{n})

$\Omega(2^n)$

Mario Carneiro

Você pode criar esse problema usando a diagonalização.

Yuval Filmus 10/10

Desculpe, eu não sigo. O que está sendo diagonalizado? Estamos enumerando problemas ou algoritmos? Como segue a dureza que não é NP?

Mario Carneiro

Você enumera as máquinas de Turing em execução no tempo reduções de tempo polinomiais, certificando-se de que nenhuma delas calcule seu idioma e nenhuma reduza o SAT para o seu idioma.

2^{n}

$2^n$

Yuval Filmus 10/10

Não. Primeiro, como Yuval aponta , o problema pode ser muito mais difícil do que o limite inferior que você provou.

Segundo, mesmo que o problema demore para resolver, não sabemos como isso se relaciona com . É possível que , caso em que qualquer problema em certamente não esteja em pelo teorema da hierarquia de tempo. Mas mesmo que , é possível que o problema requer espaço exponencial, portanto, não está em . $\Theta(2^n)$ $\mathbf{NP}$ $\mathbf{P}=\mathbf{NP}$ $\mathrm{TIME}[\Omega(2^n)]$ $\mathbf{NP}$ $\mathbf{P}\neq\mathbf{NP}$ $\mathbf{NP}$

Os melhores algoritmos que sabemos com $\mathbf{NP}$ problemas -completo levar tempo exponencial, mas você não deve presumir que "em $\mathbf{NP}$ " significa "leva tempo exponencial" ou vice-versa.

David Richerby
fonte