Je suis intéressé par la généralisation naturelle du célèbre casse-tête de 15 , dans laquelle vous devez faire glisser des blocs jusqu'à ce que vous ayez trié tous les nombres donnés (généralement, il y a un écart d'un bloc). La généralisation consisterait maintenant à étendre la taille du puzzle...
Existe-t-il un langage NP (complet de préférence naturel) , tel que pour chaque détient? En d'autres termes, contient précisément la moitié de toutes les instances à bits.L ⊆ { 0 , 1 }∗L⊆{0,1}∗L\subseteq \{0,1\}^*| L ∩ { 0 , 1 } n | = 2 n - 1 Ln ≥ 1n≥1n\geq 1 | L∩{0,1 }n| = 2n -...
L'accès à un oracle fournirait une accélération super-polynomiale majeure pour tout dans N P - P (en supposant que l'ensemble n'est pas vide). Il est cependant moins clair combien P bénéficierait de cet accès Oracle. Bien sûr, l'accélération dans P ne peut pas être super-polynomiale, mais elle peut...
László Babai a récemment prouvé que le problème d'isomorphisme des graphes est en temps quasi-polynomial . Voir également son exposé à l'Université de Chicago, note des exposés de Jeremy Kun GLL post 1 , GLL post 2 , GLL post 3 . Selon le théorème de Ladner, si P≠NPP≠NPP \neq NP , alors NPINPINPI...
Disons qu'un langage est de densité P proche s'il existe un algorithme de temps polynomial qui décide correctement sur presque toutes les entrées.LLLLLLL En d'autres termes, il existe un P , tel que disparaît, ce qui signifie Cela signifie également que sur une entrée aléatoire uniforme,...
La célèbre conjecture d'isomorphisme de Berman et Hartmanis dit que tous langages complets sont isomorphes en temps polynomiaux (p-isomorphes) les uns aux autres. La signification clé de la conjecture est qu'elle implique . Il a été publié en 1977, et une preuve à l'appui était que tous problèmes...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
Existe-t-il des problèmes NP complets sans sous-ensemble infini d'instances telles que l'appartenance à peut être décidée en temps polynomial, et pour tout , peut être résolu en temps polynomial? (En supposant )ΦΦ\PhiΦΦ\Phix∈Φx∈Φx \in \PhixxxP≠NPP≠NPP \neq
Les algorithmes de hachage de mot de passe couramment utilisés fonctionnent comme ceci aujourd'hui: salez le mot de passe et introduisez-le dans un fichier KDF. Par exemple, en utilisant PBKDF2-HMAC-SHA1, le processus de hachage de mot de passe est DK = PBKDF2(HMAC, Password, Salt, ...). Parce que...
Pour tout langage arbitraire NP complet, existe-t-il toujours un surensemble de polytimes dont le complément est également infini? Une version triviale qui ne stipule pas que le sur-ensemble a un complément infini a été demandée à /cs//q/50123/42961 Aux fins de cette question, vous pouvez supposer...
Quelle est la complexité du problème suivant? Entrée : unchemin hamiltonienen K nHHHKnKnK_n un sous-ensemble de paires de sommetsR⊆[n]2R⊆[n]2R \subseteq [n]^2 un entier positif kkk Requête : existe-t-il un correspondant tel que pour chaque , ? (où G = ( [ n ] , M ∪ H ) )MMM(v,u)∈R(v,u)∈R(v,u) \in...
Je lisais récemment un très bon article de Valiant et Vazirani qui montre que si NP≠RPNP≠RP\mathbf{NP \neq RP} , il ne peut pas y avoir d'algorithme efficace pour résoudre SAT même sous la promesse qu'il est insatisfaisant ou qu'il a une solution unique. Montrant ainsi que SAT n'admet pas...
Lorsque nous voulons prouver qu'un est N P- complet, alors l'approche standard est de montrer à L une réduction de plusieurs un calculable en temps polynomial d'un problème N P- complet connu . Dans ce contexte, nous n'avons pas besoin d'une limite stricte sur la durée de la réduction. Il suffit...
'Étant donné a,b,c∈Na,b,c∈Na,b,c\in\Bbb N , y a-t-il x,y∈Nx,y∈Nx,y\in\Bbb N , ax2+by=cax2+by=cax^2+by=c ' est NPNP\mathsf{NP} -complet. À quelle classe de complexité «Étant donné a,b,c∈Na,b,c∈Na,b,c\in\Bbb N , y a-t-il x,y∈Nx,y∈Nx,y\in\Bbb N , ax2+by2=cax2+by2=cax^2+by^2=c...
Conjecture de Berman – Hartmanis: tous les langages NP-complets se ressemblent, en ce sens qu'ils peuvent être liés les uns aux autres par des isomorphismes polynomiaux temporels [1]. Je suis intéressé par une version plus fine du "temps polynomial", c'est-à-dire si nous utilisons des réductions...
On sait depuis le début des années 70 que NPNP{\bf NP} et E=DTIME(2O(n))E=DTIME(2O(n)){\bf E}=DTIME(2^{O(n)}) ne sont pas égaux (carEE{\bf E} n'est pas fermé par des réductions de plusieurs un en temps polynomial, en revanche à NPNP{\bf NP} ). Pour autant que je sache, cependant, il est toujours...
Considérons un graphique connecté non orienté avec des poids de bord non négatifs et deux sommets distincts . Voici quelques problèmes de chemin qui sont tous de la forme suivante: trouver un chemin , de sorte qu'une fonction des poids de bord sur le chemin soit minimale. En ce sens, ils sont tous...
Je suis tombé sur un article publié dans Science "Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states" , qui fait des affirmations assez étonnantes. Memcomputing est un nouveau paradigme de calcul non-Turing qui utilise des cellules de mémoire en...