Pourquoi ne pas prendre la représentation unaire des nombres dans les algorithmes numériques?

15

Un algorithme de temps pseudo-polynomial est un algorithme qui a un temps d'exécution polynomial sur la valeur d'entrée (amplitude) mais un temps d'exécution exponentiel sur la taille d'entrée (nombre de bits).

Par exemple, tester si un nombre est premier ou non, nécessite une boucle à travers les nombres de 2 à et vérifier si mod est zéro ou non. Si le mod prend du temps O (1), la complexité temporelle globale sera O (n).nn-1n je

Mais si nous laissons être le nombre de bits requis pour écrire l'entrée, alors (binaire) donc et le temps d'exécution du problème sera O ( ) qui est exponentiel.Xx=lognn=2x2x

Ma question est, si nous considérons la représentation unaire de l'entrée , alors toujours et le temps pseudo-polynomial sera égal à la complexité temporelle polynomiale. Alors pourquoi on ne fait jamais ça?nx=n

De plus, comme il existe un algorithme pseudo-polynomial pour le sac à dos, en prenant , le sac à dos sera polynomial en conséquence P = NPx=n

M ama D
la source
3
En fait, nous le faisons, mais pas assez souvent. Pour les mêmes raisons, nous ne traitons généralement pas avec les langues unaires, mais il existe de nombreux résultats intéressants liés à ces bêtes. L'avez-vous étudié?
André Souza Lemos
2
Oui, si vous supprimez la différence entre la taille et la magnitude, vous perdez tous les concepts fondés sur cette différence.
André Souza Lemos
7
Parce que ça met le démon dans une jolie robe. Il ne fait rien de plus rapide, il rend seulement la «complexité du temps d'exécution» vide de sens.
Raphael
4
@Drupalist Le problème unaire de sac à dos n'est pas connu pour être NP-complet car la réduction normale au problème de sac à dos suppose que les nombres sont écrits en binaire. Si vous essayez de faire la réduction standard mais écrivez les nombres en unaire, la réduction ne peut pas être calculée en temps polynomial. En conséquence, le problème de sac à dos unaire étant résoluble en temps polynomial ne signifierait pas que P = NP.
templatetypedef
2
Vous voudrez peut-être consulter d'autres réponses étiquetées pseudo-polynômes , en particulier celle-ci .
Raphael

Réponses:

17

Cela signifie que le sac à dos unaire est en P. Cela ne signifie pas que le sac à dos (avec des nombres codés en binaire) est en P.

Le sac à dos est connu pour être NP-complet. Si vous montriez que le sac à dos est en P, cela montrerait que P = NP.

Mais vous n'avez pas montré que le sac à dos est en P. Vous avez montré que le sac à dos unaire est en P. Cependant, le sac à dos unaire n'est pas connu pour être NP-complet (en effet, le soupçon standard est qu'il est très probablement pas NP-complet ). Par conséquent, mettre un sac à dos unaire dans P n'implique pas que P = NP.


Alors, à quel problème devrions-nous nous préoccuper davantage, le sac à dos ou le sac à dos unaire? Si votre motivation est basée sur des préoccupations pratiques, la réponse dépendra de la taille des nombres pour lesquels vous souhaitez résoudre le problème du sac à dos: s'ils sont grands, alors vous vous souciez certainement plus du sac à dos que du sac à dos unaire. Si votre motivation est basée sur des préoccupations théoriques, alors le sac à dos est sans doute plus intéressant, car il nous permet d'avoir une compréhension plus profonde - il nous permet de faire la distinction entre taille et ampleur - tandis que le sac à dos unaire nous empêche de faire cette distinction.


Pour répondre à la question de suivi sur l'algorithme de programmation dynamique pour le problème du sac à dos:

Oui, le même algorithme de programmation dynamique peut être appliqué à la fois aux sacs à dos et au sac à dos unaire. Son temps d'exécution est polynomial dans la magnitude des nombres, mais exponentiel (pas polynomial) dans la longueur des nombres lorsqu'il est codé en binaire. Ainsi, son temps de fonctionnement est polynomial dans la longueur de l'entrée lorsque l'entrée est codée en unaire mais n'est pas polynomial dans la longueur de l'entrée lorsque l'entrée est codée en binaire. Voilà pourquoi nous ne considérons cet algorithme de programmation dynamique pour un algorithme polynomial pour unaire havresac, mais ne le considèrent comme étant un algorithme polynomial pour (codé en binaire) havresac.

Rappelons que nous disons qu'un algorithme s'exécute en temps polynomial si son temps d'exécution est au plus un polynôme de la longueur de l'entrée, en bits .

DW
la source
1
Merci beaucoup, je ne savais pas que la classe de complexité unaire et non unaire du même algorithme pouvait être différente. Pourquoi la solution de programmation dynamique du sac à dos standard ne peut pas être appliquée au sac à dos unaire, et cela a conduit à une classe de complexité différente? J'ai du mal à comprendre la version unaire des problèmes.
M ama D
@Drupalist, j'ai modifié ma réponse pour ajouter deux paragraphes à la fin pour répondre à cette question.
DW
Merci beaucoup, d'après ce que je comprends, la différence entre la taille d'entrée et son ampleur est la raison de la distinction entre polynôme et pseudo-polynôme, en utilisant une représentation unaire, j'ai essayé d'éliminer cette différence, si nous oublions le sac à dos et revenons au numérique algorithmes, je voudrais savoir en définissant quelle sera l'interprétation des polynômes et des pseudo-polynômes? Merci encoreX=n
M ama D
@Drupalist, je ne suis pas tout à fait sûr de ce que vous entendez par la définition de , donc je ne sais pas comment répondre. À ce stade, je dirais qu'il serait préférable de poser une nouvelle question (autonome) (et de définir toutes vos variables dans cette question). Cette plate-forme n'est pas si bonne pour les questions de suivi ou les va-et-vient: la meilleure façon dont nous devons la gérer est de poser une nouvelle question, en fonction de ce que vous avez appris des réponses à cette question. x=n
DW
1
@NikosM., OK, j'ai compris. Merci pour les commentaires. Personnellement, je ne crois pas que cette déclaration soit incorrecte, je vais donc la laisser telle quelle. (Mon raisonnement: la longueur de l'entrée dépend du choix de la représentation, donc je ne pense pas que cela contredit tout ce que vous avez écrit.) Cependant, il est tout à fait possible que ma perspective soit trop étroite, ou qu'une explication plus détaillée ou une explication de une perspective différente pourrait ajouter de la valeur. N'hésitez pas à écrire une réponse supplémentaire ou à suggérer une modification si vous pensez que ce point pourrait être plus clair.
DW
6

J'ajouterais une petite chose à la réponse de DW:

J'ai vu des gens qui pensent que parce que Knapsack unaire est en P, nous pouvons donc l'utiliser à la place de Knapsack dont les meilleurs algorithmes actuels ont un temps exponentiel.

Soit l'entrée = et k et considérons l'algorithme de programmation dynamique pour Knapsack et unary Knapsack. Le temps d'exécution pour les deux est O ( n k ) . C'est le même temps d'exécution. C'est-à-dire que si vous avez une entrée, peu importe si vous utilisez la programmation dynamique pour Knapsack unaire ou la programmation dynamique pour Knapsack. Les deux prendront (à peu près) le même temps pour résoudre l'instance problématique. Théoriquement, partout où vous en utilisez un, vous pouvez également utiliser l'autre. Vous avez juste besoin de convertir des nombres de unaire en binaire et vice versa.W={w1,,wn}kO(nk)

Quel est donc l'intérêt de définir la complexité des algorithmes par rapport à la taille des entrées? Pourquoi ne pas toujours les énoncer en termes de paramètres comme ?O(nk)

Si vous vous souciez d'un problème isolément, vous pouvez le faire. En fait, c'est ce que font souvent les utilisateurs d'algorithmes. La complexité des algorithmes de graphe est souvent exprimée en termes de nombre de sommets et de nombre d'arêtes, et non de la taille de la chaîne qui les code.

Mais ce n'est que lorsque nous avons affaire à un problème isolé. Il n'est pas utile lorsque nous traitons des problèmes avec différents types d'entrées. Pour les graphiques, nous pouvons parler du temps d'exécution par rapport au nombre de sommets et d'arêtes. Pour Knapsack, nous pouvons parler du nombre d'articles et de la taille du Knapsack. Mais que faire si nous voulons parler des deux? Par exemple, lorsque nous voulons réduire les problèmes ou discuter d'une classe de problèmes qui inclut des problèmes arbitraires, pas seulement ceux avec un graphique en entrée. Nous avons besoin d'un paramètre universel d'entrées. Une entrée en général n'est qu'une chaîne, c'est nous qui interprétons ses symboles comme des nombres unaires, des nombres binaires, des graphiques, etc. Pour développer une théorie générale de la complexité de l'algorithme et des problèmes, nous avons besoin d'un paramètre général des entrées. La taille de l'entrée est un choix évident et elle s'avère suffisamment robuste pour que nous puissions construire une théorie raisonnable par-dessus. Ce n'est pas la seule possibilité. Pour un artificiel, nous pouvons construire une théorie basée sur à la taille de l'entrée. Cela fonctionnera bien.2

Maintenant, nous décidons d'utiliser la taille comme paramètre universel des entrées, cela nous oblige à penser au codage des objets en termes de chaînes. Il existe différentes manières de les coder et elles peuvent avoir différentes tailles. (Ils rendent également différentes choses faciles / difficiles.) En termes de théorie générale des algorithmes, que nous codions le nombre d'entrée en unaire ou binaire devient important. Si nous utilisons unaire et que la taille de est 100, le plus grand nombre que nous obtiendrons est 100 . Si nous utilisons le binaire, k peut être aussi grand que 2 100 - 1 . Donc, quand nous parlons du temps d'exécution de la résolution des problèmes de sac à dos où la taille de kk100100k21001kk21001

nnp(n)kp(n)k2p(n)1kk

nk

Kaveh
la source
Merci beaucoup, encore une question, en convertissant l'entrée en sa représentation unaire, qu'arrivera-t-il au problème de déterminer si un nombre est premier ou non? Ce problème est polynomial basé sur la grandeur d'entrée mais exponentiel basé sur les bits d'entrée (comme je l'ai souligné dans la question), cette conversion améliorera-t-elle quelque chose?
M ama D du
nO(n)nb=210241210241210241
Kaveh
belle clarification, mais jetez un oeil à mon commentaire sous la réponse de DW qui est liée à ce post
Nikos M.
2

En bref et simple, je vais vous montrer pourquoi.

Tally

x = input integer

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

xxO(2n)

Tally/UnaryO(n)x

x = input tallies

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

La représentation d'entrée ne rend pas le code plus rapide. Même si le 2ème algorithme est vraiment poly-temps. Ce n'est pas très pratique pour trouver les facteurs de RSA.

Travis Wells
la source
Bel exemple, merci
M ama D