Y at-il des problèmes qui deviennent plus faciles avec leur taille?

62

C'est peut-être une question ridicule, mais est-il possible d'avoir un problème qui devient réellement plus facile à mesure que les intrants grossissent? Je doute que des problèmes pratiques se présentent de la sorte, mais peut-être pourrions-nous inventer un problème dégénéré qui possède cette propriété. Par exemple, il commence peut-être à se «résoudre» à mesure qu’il grandit ou à se comporter d’une autre manière bizarre.

Dsaxton
la source
7
Un problème réel avec cette propriété qui me vient à l’esprit est le craquage du hachage du mot de passe non salé comme suit: «Donné n hachages, craquez au moins un hachage». Etant donné que la vitesse de fissuration serait linéaire avec n, le temps d'exécution serait proportionnel à 1 / n - sauf que nous ne pouvons pas réellement attribuer de temps définitif car la fissuration est stochastique et n'a pas de limite supérieure constante dans le temps.
amon
1
@amon Le temps d'exécution n'est pas comme . Il faut du temps juste pour lire le vous hash avez reçu en entrée! n n1/nnn
David Richerby
3
Voulez-vous dire plus facile en termes absolus ou relatifs? Quelles mesures de coût autorisez-vous? Avez-vous besoin d'un coût strictement décroissant, ou est-ce suffisant de ne pas augmenter (à partir d'un certain point)?
Raphaël
2
@DavidRicherby Dans cet exemple, il est légitime d'ignorer le coût de la lecture de l'entrée tant que je ne fais aucune déclaration sur le coût absolu. Au lieu de cela, la vitesse augmente linéairement avec l'entrée. Par conséquent, n • T (1)> T (n) même en considérant le coût de lecture de l'entrée. C'est-à-dire que pour ce problème, il est plus facile de résoudre une entrée volumineuse en une fois que de scinder l'entrée en entrée, même si le problème est divisible. Je ne dis pas que T (n)> T (n + 1) pour tout n.
amon
4
Pour tous ceux qui souhaitent publier une autre réponse du formulaire, "Un problème où la saisie est une question plus une foule d'indices sur la réponse": Cela ne fonctionne pas. Les entrées les plus difficiles de longueur sont celles où vous utilisez tous les bits pour poser la question sans donner d'indices. Le fait qu'il soit facile de traiter des questions courtes avec beaucoup d'indices ne signifie pas que la durée d'exécution dans le pire des cas est bonne. nnn
David Richerby

Réponses:

39

Non, ce n’est pas possible: du moins, pas dans un sens asymptotique, où vous avez besoin que le problème continue de s’obtenir strictement plus facile, pour toujours, comme .n

Soit le meilleur temps d'exécution possible pour résoudre un tel problème, où est la taille de l'entrée. Notez que le temps d'exécution est un décompte du nombre d'instructions exécutées par l'algorithme, il doit donc s'agir d'un entier non négatif. En d'autres termes, pour tout . Maintenant, si nous considérons une fonction , nous voyons qu’il n’existe pas de telle fonction décroissante de façon strictement monotone. (Quel que soit , il doit être fini, disons ; mais comme est monotone décroissant, etn T ( n ) N n T : NN T ( 0 ) T ( 0 ) = c T T ( c ) 0 T ( c + 1 ) - 1 T ( n ) n 0 n n 0 T ( n )T(n)nT(n)NnT:NNT(0)T(0)=cTT(c)0T(c+1)1, ce qui est impossible.) Pour des raisons similaires, il n’existe pas de fonction décroissante asymptotiquement: on peut de même prouver qu’il n’existe pas de fonction de temps où il existe tel que pour tout , est strictement décroissante de façon monotone (toute fonction de ce type devrait finir par devenir négative).T(n)n0nn0T(n)

Un tel problème ne peut donc pas exister pour la simple raison que les durées d'exécution doivent être des entiers non négatifs.


Notez que cette réponse ne couvre que les algorithmes déterministes (c'est-à-dire le temps d'exécution le plus défavorable). Il n’exclut pas la possibilité d’algorithmes aléatoires dont la durée d’exécution attendue décroît de façon strictement monotone, pour toujours. Je ne sais pas s'il est possible qu'un tel algorithme existe. Je remercie Beni Cherniavsky-Paskin pour cette observation .

DW
la source
9
C'est une belle preuve, mais je ne suis pas d'accord avec le principe. Au lieu de demander un temps d’exécution décroissant de façon strictement monotone, la question pourrait plus raisonnablement exiger une fonction s’il existe un a, b avec a <b, de sorte que T (a)> T (b), c’est-à-dire sa décroissance non strictement monotone. Ensuite, il est bien sûr possible de trouver des fonctions entières appropriées. Mais pourquoi des entiers? J'avais l'impression que le temps en cours correspond à un temps et non à un nombre d'instructions (sauf bien sûr pour les machines de Turing), et que l'expression T pourrait utiliser des opérations non entières comme log () ou des exposants non entiers.
amon
2
@amon "le temps d'exécution désignait une heure, pas un nombre d'instructions" Absolument pas. Le temps d'exécution est toujours un nombre d'instructions. Tout le reste serait impossible à raisonner car cela dépendrait insensiblement de nombreux détails de mise en œuvre.
David Richerby
3
Aussi vague que soit la question, je ne vois pas en quoi une fonction de coût de, disons, , est exclue . Maintenant, mais pour "petit" , donc le problème "devient plus facile", relativement parlant. (Les coûts absolus croissent de manière asymptotique, bien sûr). T ( n ) ~ n T ( n ) n 2 nT(n)=n2(1+ϵ)n+nT(n)nT(n)n2n
Raphaël
2
@Raphael, n’est pas un problème pour devenir plus facile: s’agrandit à mesure que s’agrandit, alors le problème devient plus difficile à mesure que grandit, une fois que est suffisamment grand. Dans la première phrase de ma réponse, j’ai déclaré qu’aucun problème ne pouvait continuer à s’améliorer pour toujours. Bien sûr, un problème peut devenir plus facile pendant un petit moment ( peut diminuer pour , disons), mais il ne peut pas continuer à s’aggraver pour toujours. T ( n ) n n n T ( n ) n cT(n)nT(n)nnnT(n)nc
DW
1
Même avec des temps entiers, pour un algorithme randomisé , le temps attendu (ou toute autre mesure de la distribution) peut être fractionnaire et pourrait progressivement s'approcher d'une constante du haut. [Cela ne signifie pas que de tels problèmes existent réellement, mais que l' argument "pas de fonction existe" est insuffisant.]T
Beni Cherniavsky-Paskin
25

Bien que ce ne soit pas tout à fait une réponse à votre question, l' algorithme de recherche de chaînes de Boyer-Moore s'en rapproche. Comme Robert Moore le dit sur sa page Web à propos de l'algorithme,

Notre algorithme a la propriété particulière que, grosso modo, plus le motif est long, plus l'algorithme va vite.

En d'autres termes, l'algorithme recherche généralement une instance d'une chaîne cible dans une chaîne source et une chaîne source fixe, plus la chaîne cible est longue, plus l'algorithme s'exécute rapidement.

Rick Decker
la source
10
On peut soutenir que le motif ne correspond pas à la taille du problème, mais à la longueur de la chaîne recherchée. Comme dans le commentaire de David Richerby ci - dessus , je dirais que la longueur du motif est plus une indication de la façon de résoudre le problème (au sujet de la recherche de la chaîne) que du problème lui-même (voir si un motif correspond à une chaîne d'une longueur particulière .)
Kevin - Réintégrer Monica
4
@Kevin La déclaration suggère que la recherche d'un motif de longueur dans une longueurn, letexte est plus rapide que la recherche d’un modèle de longueurlogn. En regardant de telles entrées à relation fixe (c.-à-d. Paires de chaînes), je pense que Rick a donné une réponse appropriée à la question (si ce n’est au sens classique, asymptotique). nnlogn
Raphaël
10

Clairement, d'un point de vue purement mathématique, purement algorithme CS, cela est impossible. Mais en réalité, il existe plusieurs exemples concrets de la simplification de la mise à l'échelle de votre projet, dont beaucoup ne sont pas intuitives pour les utilisateurs finaux.

Directions : plus vos directions sont longues, plus elles deviennent parfois plus faciles. Par exemple, si je veux que Google Maps me donne des indications pour aller à l'ouest sur une distance de 3000 km, je pourrais me rendre sur la côte ouest et obtenir des instructions de conduite pour tout le pays. Mais si je voulais aller à 6000 km à l’ouest, je me retrouverais avec des instructions beaucoup plus simples: prendre un avion de New York à Hokkaido. Me donner une route de fond qui intègre le trafic, les routes, la météo, etc. est assez difficile sur le plan algorithmique, mais me dire de monter dans un avion et de rechercher des vols dans une base de données est comparativement beaucoup plus simple. Graphique ASCII de difficulté vs distance:

           |     /
           |    /
Difficulty |   /                  ____-------
           |  /           ____----
           | /    ____----
            ---------------------------------
                       Distance

Rendu : disons que je veux un rendu d'un visage et un rendu de 1000 visages; il s’agit d’une annonce publicitaire, les deux images finales doivent donc être de 10 000 pixels par 5 000 pixels. Rendre un visage réaliste serait difficile - avec une résolution de plusieurs milliers de pixels, vous devez utiliser des machines très puissantes - mais pour une foule de 1 000 visages, chaque visage ne doit comporter que dix pixels de large et peut facilement être cloné! Je pourrais probablement restituer 1000 visages sur mon ordinateur portable, mais rendre un visage réaliste à 10000 pixels de large prendrait beaucoup de temps et nécessiterait des machines puissantes. Graphique ASCII de difficulté par rapport aux objets rendus, montrant comment la difficulté de rendre n objets en une image d'une taille définie disparaît rapidement, puis revient lentement:

           | -    
           |- -                     _________
Difficulty |   --      ______-------            
           |     ------      
           |       
            ---------------------------------
                        Objects

Contrôle du matériel : beaucoup de choses avec le matériel deviennent beaucoup plus faciles. "Déplacer le moteur X 1 degré" est difficile et / ou impossible, et vous devez faire face à toutes sortes de choses que vous n'auriez pas à traiter pour "déplacer le moteur X 322 degrés".

Tâches de courte durée: Disons que vous souhaitez que l'élément X soit activé (très peu de temps) toutes les secondes. En augmentant la durée d'exécution de X, vous aurez besoin de logiciels et de matériel moins complexes.

Owen Versteeg
la source
Dans votre exemple "directions", veuillez indiquer exactement quel est le problème de calcul et quelle est l'instance. Il n’est pas du tout clair pour moi que votre exemple de 6 000 km soit une instance plus grande ou juste un exemple d’une partie facile de quelque chose (par exemple, si je vous donne un grand graphe connecté avec un sommet isolé, demandant en général les plus courts chemins "difficile", mais demander le chemin le plus court du sommet isolé à n’importe où est trivial). Encore une fois, pour votre exemple de rendu, quel est le problème de calcul actuel? Quelle est l'instance par rapport à laquelle vous mesurez la complexité?
David Richerby
L'exemple de rendu ne semble pas être le cas du même problème: le premier est le rendu d'une seule image; la seconde consiste à restituer de nombreuses petites images puis à coller plusieurs copies de ces images dans une zone donnée.
David Richerby
Je pense que pour voyager, les paramètres seraient le nom des 2 villes et n le nombre de caractères pour les encoder.
Emory
3

Il y a des cas. Ce sont les cas où le critère de succès est fonction des données plutôt que d'essayer de trouver une réponse unique. Par exemple, les processus statistiques dont les résultats sont formulés avec des intervalles de confiance peuvent devenir plus faciles.

Un cas particulier auquel je pense est celui des problèmes qui passent de comportements discrets à des comportements continus, tels que les écoulements de fluide. Résoudre le petit problème avec un degré d'erreur maximum peut impliquer la modélisation de toutes les interactions discrètes, ce qui peut nécessiter un superordinateur. Les comportements continus permettent souvent des simplifications sans donner de résultats en dehors d’une erreur corrélée.

Cort Ammon
la source
2

La question est intéressante et UTILE, car notre philosophie en informatique est de résoudre les problèmes plus nous lisons, plus la lecture est difficile. Mais, en réalité, la plupart des problèmes présentés de manière typique (difficile) peuvent être facilement représentés de manière "facile"; même en connaissant la réponse de DW (ce qui est faux en considérant que facile ne veut pas dire plus vite, veut dire "moins lent"; vous n'avez donc pas à trouver des moments négatifs, vous avez peut-être à trouver des moments asymptotiques).

L'astuce pour en trouver un consiste à mettre la partie de la solution comme une indication comme entrée et à considérer l'entrée du problème comme un paramètre constant.

Exemple: Quel est le plus long trajet en voiture entre Londres et Paris en évitant de visiter deux villes française et britannique et de ne pas visiter d’autres pays? considérez, vous devez aller à Birmingham avant Ashford, Orléans avant Versailles, La Rochelle avant Limoge, etc ...

Il est clair que ce problème avec les entrées longues sera plus facile qu'avec les entrées courtes.

Exemple d’utilisation: Imaginez un jeu géré par la machine et l’IA de l’ordinateur doit déterminer s’il doit explorer davantage le jeu pour trouver plus d’allusions, sinon, si le moment est venu de déduire quelle est la meilleure décision à prendre .

Juan Manuel Dato
la source
2
Votre exemple ne fonctionne pas. Les instances volumineuses, car elles contiennent de nombreuses astuces, ce qui facilite la détermination d'un ordre linéaire des sommets du graphique. Cependant, les instances volumineuses, car elles fournissent un graphique volumineux avec pratiquement aucune indication, sont aussi difficiles à résoudre que le problème du chemin Hamiltonien ordinaire. Ainsi, le temps d'exécution le plus défavorable de tout algorithme permettant de résoudre ce problème sera au moins aussi mauvais que le temps d'exécution le plus défavorable du meilleur algorithme pour le chemin hamiltonien, qui ne semble pas être "super facile".
David Richerby
@ David, votre réponse est complètement incorrecte: 1. L'entrée n'est pas un graphique: le grand graphique est un PARAMÈTRE. Le problème hamiltonien est donc converti en une constante (très grande, mais constante). 2. L'entrée est la solution du problème, donc: si vous êtes plus grand, vous offrez une explossion combinatoire d'indices. Une entrée d'un indice donne une aide, deux conseils le double, trois conseils seront près de 4 deux fois ..., car vous éliminez les solutions possibles. Donc, ce n’était pas un hamiltonien, c’est une solution issue d’un graphe spécifique et le problème est de savoir QUOI faire avec certaines parties des solutions.
Juan Manuel Dato
Je pense que votre argument est intéressant dans la mesure où les grandes instances sont "plus faciles" dans un sens, mais je pense que la réponse à la question initiale est finalement "non". Puisque le graphe est fini, il n’ya donc que très peu d’indices possibles. Par conséquent, chaque instance peut être résolue en temps constant (par exemple, à l'aide d'une table de recherche). Même si de plus grandes instances sont (intuitivement) plus faciles dans la vue informatique (asymptotique), toutes les instances sont également dures (résolvables en temps constant).
Tom van der Zanden
@Tom, je suis d'accord que votre attention à la complexité sera constante, mais le problème est de savoir comment nous acceptons les nouvelles indications: si avec notre philosophie de calcul de l'entrée longue n'est pas meilleure qu'une entrée courte, alors nous devons changer notre philosophie - Parce que c'est un fait: les entrées longues impliquent des problèmes plus faciles. Donc, nous ne pouvons pas travailler de cette façon ... Je recommanderais mon livre, mais je n'ai aucune réputation ...
Juan Manuel Dato
nlogn
1

Prenons un programme qui prend en entrée ce que vous savez sur un mot de passe, puis tente de le déchiffrer. Je pense que cela fait ce que tu veux. Par exemple:

  • Pas d'entrée-> La force brute craque sur tous les symboles et un mot de n'importe quelle longueur
  • Longueur du mot de passe -> Force brute de tous les symboles d'un mot de cette longueur
  • Symboles contenus -> Réduit la liste des symboles à vérifier
  • ...
  • Symboles contenus incluant les occurrences multiples et la longueur -> Calculer uniquement les permutations
  • Tous les symboles dans le bon ordre -> fondamentalement résolu

Je devrais ajouter que c’est un truc, car le problème énoncé est inverse à la taille de la saisie. Vous pouvez laisser de côté une couche d'abstraction et dire que la taille d'entrée est grande sans entrée (vérifiez tous les symboles et la longueur des mots) et petite si vous entrez le mot de passe correct au début.

Donc, tout dépend de l'abstraction que vous permettez.

RunOrVeith
la source
2
b
0

En fait, j'ai un problème qui diminue à mesure que les données augmentent. L'une de mes applications enregistre les attributs d'un produit particulier, par exemple le fromage. Les attributs sont par exemple le type de fromage, la marque, le pays, la région, le type de lait, etc. Chaque mois environ, je reçois une liste des nouveaux fromages arrivés sur le marché pendant cette période, ainsi que leurs attributs. Maintenant, ces attributs sont typés à la main par un groupe d'humains. Certains font des fautes de frappe ou ne connaissent tout simplement pas la valeur de tous les attributs.

Lorsque vous effectuez une recherche dans ma base de données, j'essaie de prédire à partir de statistiques le goût du fromage, en fonction de ces attributs. Qu'est-ce qui se passe, c'est que pour chaque attribut, je me retrouve avec une plage de valeurs; certains sont valides, d'autres sont invalides. L'élimination ou la correction de ces invalides n'est possible que si j'ai suffisamment de données. Il s'agit de faire la différence entre les valeurs réelles et le bruit, sans éliminer les valeurs rares mais valables.

Comme vous pouvez l’imaginer, avec un faible volume, le bruit est trop important pour que tout soit réglé correctement. Si vous avez 5 instances de Cheddar, 1 de Brie, 1 de Bri et 1 de Chedar, comment puis-je savoir lequel est correct et lequel est une faute de frappe? Avec plus de volume, les fautes de frappe ont tendance à rester très bas, mais les valeurs rares obtiennent quelques incréments cruciaux, les faisant échapper au bruit (adossé à l'expérience). Dans ce cas, je pourrais par exemple imaginer 50000 cheddar, 3000 brie, 5 bri, 15 chédar.

Alors oui, certains problèmes se résolvent d'eux-mêmes lorsque vous avez suffisamment de données.

chris
la source
1
Cela échoue pour la raison habituelle. Une contribution importante pourrait être une entrée dans laquelle les gens vous parleraient de nombreux types de fromage, plutôt que dans laquelle ils vous parleraient de quelques sortes de fromage mais certains d'entre eux l'orthographieraient mal. En outre, il n'est pas clair que "plus facile" soit censé être interprété comme "permet une plus grande confiance dans le résultat".
David Richerby
C'est un problème réel (je l'ai déjà eu deux fois), qui ne peut pas être résolu avec une faible quantité de données. Cela peut, et il est même plus facile de distinguer les bonnes valeurs des mauvaises, au fur et à mesure que le volume augmente. Il a le mérite de répondre à la question "Y a-t-il des problèmes qui deviennent plus faciles avec leur taille?" Peu importe le nombre de types de fromages qui finissent par arriver, avec suffisamment de volume, ils auront plus de "hits" que les fautes de frappe. C’est cs .stackexchange, pas des maths, donc les problèmes sont différents et leur résolution consiste parfois simplement à avoir une plus grande confiance dans les résultats.
chris
N'est-ce pas aussi une sorte de prémisse de la série télévisée Numbers ? Ou au moins quelques épisodes - je sais que je me souviens spécifiquement d'une scène où le mathématicien remarque que l'algorithme qu'il utilise pour résoudre le problème actuel devient plus efficace avec un jeu de données plus volumineux.
Dan Henderson
2
"Gets plus efficace"! = "Devient plus facile".
David Richerby
-1

Considérons le problème NP-complet 3-SAT. Si vous continuez à augmenter le problème en fournissant des entrées de la forme x_i = true / false, vous finissez par convertir les disjonctions individuelles en clauses à deux variables, créant ainsi un problème à 2 SAT résolument P, ou vous obtenez simplement une réponse vraie / fausse.

Dans le cas où il y a redondance dans les entrées x_i = true / false (même entrée fournie plusieurs fois, ou entrées contradictoires), vous pouvez facilement trier les entrées et ignorer les valeurs redondantes ou signaler une erreur si les valeurs sont en contradiction.

Dans tous les cas, je pense que cela représente un problème «réaliste» qui devient plus facile à résoudre à mesure que le nombre d’entrées augmente. L'aspect «plus facile» consiste à convertir un problème NP-complet en un problème P. Vous pouvez toujours jouer avec le système en fournissant des entrées ridicules telles que le tri prendrait plus de temps que forcer brutalement le problème.

Maintenant, un scénario vraiment cool serait que si nous sommes prêts à accepter, T (0) (en utilisant la notation de DW dans la réponse ci-dessus) peut être infini. Par exemple, T (0) pourrait être équivalent à résoudre le problème de Halting de Turing. Si nous pouvions concevoir un problème tel que l'ajout d'intrants supplémentaires le convertisse en un problème pouvant être résolu, nous aurions trouvé de l'or. Notez qu'il ne suffit pas de le convertir en un problème pouvant être résolu de manière asymptotique - car c'est aussi grave que de forcer le problème.

v vv cvvcv
la source
1
Ces entrées particulières deviennent plus faciles. Cependant, lorsque vous considérez toutes les entrées possibles, 3SAT est généralement beaucoup plus difficile à ajouter au fur et à mesure que vous ajoutez des clauses: les entrées fermes sont celles sans ces clauses "hint". Si vous n'autorisez pas les entrées générales, vous devez indiquer exactement quelles entrées vous autorisez.
David Richerby
Tout d'abord, nous sommes d'accord pour dire que l'ajout d'intrants peut augmenter le temps d'exécution. Je dis essentiellement la même chose ci-dessus. Deuxièmement, je dis clairement que nous prenons un 3-SAT existant et ajoutons uniquement des entrées de la forme x_i = true / false. Je pense que cela est suffisamment clair et je n'ai pas besoin de clarifier davantage. Je pense que vous prenez la peine de donner l'interprétation la plus mal interprétée de ce que j'ai écrit. S'il vous plaît ne vous dérange pas.
vvv cvvcv
1
Non sérieusement. Quel problème informatique résolvez-vous? Un problème de calcul consiste à décider de l'appartenance à un ensemble de chaînes (disons un ensemble de formules pour éviter les désagréments liés au codage). Quel est l'ensemble de formules pour lequel vous prétendez qu'il est plus facile de décider si une formule longue est dans l'ensemble que de décider qu'une formule courte est dans l'ensemble? Dès que vous essayez de préciser cela, je suis presque sûr que votre demande s'effondrera.
David Richerby
Pouvez-vous s'il vous plaît expliciter votre compréhension de «ma demande»? Dès que vous essayez de préciser cela, je suis certain que vous cesserez de gaspiller la bande passante Internet.
vvv cvvcv
Je suis un informaticien, pas un lecteur d'esprit. Rendre votre réclamation précise est votre travail, pas le mien.
David Richerby
-1

La question demande: "est-il possible d'avoir un problème qui devient réellement plus facile à mesure que les intrants grossissent?" Que se passe-t-il si les entrées sont des ressources à utiliser par l'algorithme pour travailler sur un travail? Tout le monde sait que plus il y a de ressources, mieux c'est. Vous trouverez ci-dessous un exemple dans lequel plus il y a d'employés, mieux c'est.


n
tp


n

3) Sortie:
La sortie représente les chemins entre les tâches à prendre par les employés. Chaque chemin est associé au nombre d'employés qui le suivent. Par exemple:

n1
n2
n3
n4
n5

4) Solution possible:
Une solution possible consiste à calculer d’abord le chemin le plus court vers les nœuds les plus proches, à partir de A. Ce sera un chemin aller. Ensuite, calculez récursivement le chemin de transfert pour chaque tâche visitée. Le résultat est un arbre. Par exemple:

          UNE
      avant JC
    DE

nn1n2n20

n=n=1

n

Yemelitc
la source
6
Merci d'avoir partagé vos pensées. Normalement, en informatique, un algorithme est censé accepter une séquence de bits en entrée et générer une autre séquence de bits. Avec cette compréhension standard, je ne vois pas comment cette réponse peut avoir un sens. Si vous avez une notion différente de l’algorithme en tête, je pense qu’il serait utile de modifier la question afin de décrire ce que vous entendez par algorithme terme, si je comprends bien).
DW
L'entrée peut simplement être un nombre (le nombre de ressources). Cela affectera le nombre de calculs supplémentaires que l'algorithme devra effectuer. Je vais modifier la réponse pour fournir un exemple plus concret.
mardi
Merci pour votre modification - cela le rend beaucoup plus clair. Je vois maintenant que vous ne confondez pas les coûts de calcul de la solution avec ceux de son exécution, comme je le pensais au départ. Mais maintenant nous sommes dans la situation habituelle. Premièrement, il faut au moins un temps linéaire pour lire l'entrée. Deuxièmement, les cas difficiles ne sont pas ceux où vous donnez un petit arbre et un million de personnes, mais où vous donnez un grand arbre et relativement peu de personnes. (Par exemple, si vous me permettez un million de bits, je choisirai un arbre avec environ mille sommets et vous donnerai cinq personnes, pas un arbre avec cinq sommets et mille personnes.)
David Richerby Le
Je suis d'accord. Il semble que nous ayons tous fini par être assez critiques à ce sujet, contrairement à ce que la question initiale nous tentait de faire! Mais j'espère que vous aurez mon idée de «contribution en tant que ressource»: peu importe l'ampleur du travail, plus il y a de personnes, mieux c'est. Toujours dans un sens asymptotique, vous avez certainement raison, je devrais tout simplement blâmer les entiers non négatifs.
mardi