Si la limite inférieure d'un problème est exponentielle, est-ce NP?

En supposant que nous avons un problème et nous avons montré que la borne inférieure pour résoudre est . $p$ $p$ $\mathcal{\Omega}(2^n)$

la borne inférieure impliquer le problème dans ? $\mathcal{\Omega}(2^n)$ $NP$

time-complexity np-complete Kelalaka
la source

Ce n'est pas NP mais c'est NP-difficile.

user35734

Comment savez-vous que c'est NP-difficile?

Yuval Filmus

Si vous pouviez montrer qu'un problème se trouve à la fois dans et dans NP, vous auriez prouvé P NP.

Ω (2^{n})

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

\neq

$\neq$

kasperd

@kasperd: Nous appelons cela les puzzles de Merkle, mais il devrait être exclu de P =? NP parce que la forme spécifique ne donne aucun autre avec les mêmes propriétés et une preuve de P = NP sinon élimine probablement tout moyen de faire des puzzles de Merkle qui fonctionnent réellement comme prévu. Le temps exponentiel des puzzles de Merkle est également PSPACE pour l'utilisateur prévu.

Joshua

Les puzzles de @Joshua Merkle ne sont pas exponentiels en fonction de la longueur d'entrée . (Eh bien, si nous supposons que la solution pour Alice est polynomiale).

rus9384

Réponses:

Non. Par exemple, le problème d'arrêt a une borne inférieure , mais il n'est pas dans NP (car il n'est pas calculable). $\Omega(2^n)$

Le théorème de la hiérarchie temporelle non déterministe montre que tout problème NEXP-complet est un autre exemple (avec potentiellement remplacé par une fonction exponentielle plus petite ). $2^n$ $c^{n^\epsilon}$

NP est une limite supérieure de la complexité d'un problème.

Yuval Filmus
la source

Pourriez-vous donner un exemple d'un problème qui est mais pas NP-hard?

Ω (2^{n})

$\Omega(2^n)$

Mario Carneiro

Vous pouvez construire un tel problème en utilisant la diagonalisation.

Yuval Filmus

Désolé, je ne suis pas. Qu'est-ce qui est diagonalisé? Sommes-nous en train d'énumérer des problèmes ou des algorithmes? Comment suit la dureté non NP?

Mario Carneiro

Vous énumérez à la fois les machines Turing fonctionnant dans le temps et les réductions de temps polynomiales, en vous assurant qu'aucune des premières ne calcule votre langue et qu'aucune des dernières ne réduit SAT à votre langue.

2^{n}

$2^n$

Yuval Filmus

Tout d'abord, comme le souligne Yuval , le problème pourrait être beaucoup plus difficile que la borne inférieure que vous avez prouvée.

Deuxièmement, même si le problème prend du temps à pour être résolu, nous ne savons pas comment cela se rapporte à . Il est possible que , auquel cas tout problème dans soit certainement pas dans par le théorème de la hiérarchie temporelle. Mais même si , il est possible que le problème nécessite un espace exponentiel donc il n'est pas dans . $\Theta(2^n)$ $\mathbf{NP}$ $\mathbf{P}=\mathbf{NP}$ $\mathrm{TIME}[\Omega(2^n)]$ $\mathbf{NP}$ $\mathbf{P}\neq\mathbf{NP}$ $\mathbf{NP}$

Les meilleurs algorithmes que nous connaissons pour les problèmes complétés par prennent du temps exponentiel mais vous ne devez pas supposer que "dans " signifie "prend du temps exponentiel" ou vice versa. $\mathbf{NP}$ $\mathbf{NP}$

David Richerby
la source