Y a-t-il un problème naturel sur les produits naturels qui est NP-complet?

Tout nombre naturel peut être considéré comme une séquence de bits, donc la saisie d'un nombre naturel est la même que la saisie d'une séquence 0-1, donc des problèmes NP-complets avec des entrées naturelles existent évidemment. Mais y a-t-il des problèmes naturels, c'est-à-dire ceux qui n'utilisent pas d'encodage et d'interprétation spéciale des chiffres? Par exemple, "Est-ce que na prime?" est un problème si naturel, mais celui-ci est en P. Ou "Qui gagne le jeu Nim avec des tas de taille 3, 5, n, n?" est un autre problème que je considère naturel, mais nous savons aussi que c'est dans P. Je suis également intéressé par d'autres classes de complexité au lieu de NP.

Mise à jour: Comme l'a souligné Emil Jeřábek, étant donné pour déterminer si a une solution par rapport aux naturels est NP-complet. C'est exactement ce que j'avais en tête comme naturel, sauf qu'ici l'entrée est de trois nombres au lieu d'un seul.a x 2 + b y - c = $a,b,c\in \mathbb N,$$ax^2+by-c=0$

Mise à jour 2: Et après plus de quatre ans d'attente, Dan Brumleve a donné une "meilleure" solution - notez qu'elle n'est toujours pas complète en raison de la réduction aléatoire.

Ce problème a une variation avec une seule entrée entière:

t -il un diviseur strictement entre ses deux plus grands facteurs premiers?$n$

L'idée est d'utiliser la même réduction aléatoire de la somme des sous-ensembles décrite dans la réponse du haut à la question liée, mais avec la plage cible codée comme les deux plus grands premiers au lieu d'être donnée séparément. La définition a un aspect naturel même si ce n'est qu'une fonction d'appariement déguisée.

Voici une autre variante du même problème, avec une réduction similaire du problème de partition:

est-il le produit de deux entiers qui diffèrent de moins de ?n $n$$n^{\frac{1}{4}}$

Dans les deux réductions, nous «camouflons» un ensemble d'entiers en trouvant des nombres premiers proches et en prenant leur produit. S'il est possible de le faire en temps polynomial, alors ces problèmes sont NP-complets.

Je pense qu'il est éclairant de regarder ces exemples avec le théorème de Mahaney : si et que nous pouvons trouver des nombres premiers proches, alors ces ensembles ne sont pas rares. Il est satisfaisant d'obtenir une déclaration purement arithmétique de la théorie de la complexité (même si elle n'est que conjecturale et est probablement facilement prouvable d'une autre manière).$P \ne NP$

Sur la base de la discussion, je republierai ceci comme une réponse.

Comme l'ont démontré Manders et Adleman , le problème suivant est NP-complet: étant donné les nombres naturels , déterminez s'il existe un nombre naturel tel que .x ≤ c x 2 ≡ $a,b,c$$x\le c$$x^2\equiv a\pmod b$

Le problème peut être indiqué de manière équivalente comme suit: étant donné , déterminer si le quadratique a une solution .x 2 + b y - c = 0 x , y ∈ $b,c\in\mathbb N$$x^2+by-c=0$$x,y\in\mathbb N$

(Le document original énonce le problème avec , mais il n'est pas difficile de voir que l'on peut le réduire au cas )a = $ax^2+by-c$$a=1$

Voici un problème -complet avec un seul nombre naturel comme entrée.$\text{NEXP}$

Le problème concerne le carrelage d'une grille avec un ensemble fixe de tuiles et des contraintes sur les tuiles adjacentes et les tuiles sur la frontière. Tout cela fait partie de la spécification du problème; il ne fait pas partie de l'entrée. L'entrée n'est que le nombre . Le problème est -complet pour un certain choix de règles de tuilage comme indiqué dans$n \times n$$n$$\text{NEXP}$

D. Gottesman, S. Irani, «La complexité quantique et classique des problèmes de pavage translationnellement invariants et des problèmes hamiltoniens», Proc. 50e Symp annuel. on Foundations of Computer Science, 95-104 (2009), DOI: 10.1109 / FOCS.2009.22 . Aussi arXiv: 0905.2419 .

Le problème est défini à la page 5 de la version arxiv.

De plus, ils définissent également un problème similaire qui est -complete, qui est l'analogue quantique d'erreur bornée de . (L'analogue d'erreur borné classique de est .) NEXP NEXP MA $\text{QMA}_\text{EXP}$$\text{NEXP}$$\text{NEXP}$$\text{MA}_\text{EXP}$

Je pense qu'en utilisant l'une des variantes limitées dans le temps de la complexité de Kolmogorov, vous pouvez créer un problème qui utilise uniquement la représentation binaire d'un nombre et (je pense) ne sera probablement pas dans ; informellement, il s'agit d'une version décidable du problème "Est-ce que est compressible?":$\mathsf{P}$$n$

Problème: Étant donné , existe- t-il une machine de Turing telle que et sur une bande vierge sort en moins de étapes, où est la longueur de la représentation binaire deM | M | < l M n l 2 l = ⌈ log n ⌉ $n$$M$$|M| < l$$M$$n$$l^2$$l = \lceil \log{n} \rceil$$n$

Il est clairement dans , car étant donné et , simulez simplement pour étapes et s'il s'arrête, comparez le résultat avec . n M M l 2$\mathsf{NP}$$n$$M$$M$$l^2$$n$

Notre article FOCS'17 sur l'arithmétique du short presburger est un exemple d'un problème "naturel" qui est NP-c, et utilise un nombre constant d'entiers dans l'entrée, disons . Il diffère de Manders-Adleman en ce que les contraintes sont toutes des inégalités. Voir le blog de Gil Kalai pour un aperçu. $C$$C< 220$

Que diriez-vous du problème de PARTITION ?