Chaque langage indécidable reconnaissable par Turing a-t-il un sous-ensemble NP-complet? La question pourrait être considérée comme une version plus forte du fait que chaque langue infinie reconnaissable par Turing a un sous-ensemble décidable
Cette question s'est posée dans le contexte de la cryptographie, mais je la présenterai ci-dessous en termes de théorie de la complexité, car les gens ici connaissent mieux cette dernière. Cette question est liée à des problèmes dans NP mais pas dans Average-P / poly et Beating Nonuniformity par...
Supposons que P! = NP. Nous savons que nous pouvons à tout moment créer des instances simples de 3-SAT. Nous pouvons également générer ce que nous pensons être des instances dures (car nos algorithmes ne peuvent pas les résoudre rapidement). Y a-t-il quelque chose qui empêche l'ensemble d'instances...