Des exemples du prix de l'abstraction?

L'informatique théorique a fourni quelques exemples du "prix de l'abstraction". Les deux plus importants concernent l'élimination et le tri gaussiens. À savoir:

• On sait que l'élimination gaussienne est optimale pour, par exemple, calculer le déterminant si vous limitez les opérations à des lignes et à des colonnes dans leur ensemble [1]. Bien entendu, l'algorithme de Strassen n'obéit pas à cette restriction et il est asymptotiquement meilleur que l'élimination gaussienne.
• Dans le tri, si vous traitez les éléments de la liste comme des boîtes noires ne pouvant être comparées et déplacées, nous avons la limite inférieure standard $n \log n$ théoriques de l'information. Pourtant, les arbres de fusion dépassent cette limite en utilisant, autant que je sache, une utilisation intelligente de la multiplication.

Existe-t-il d'autres exemples du prix de l'abstraction?

Pour être un peu plus formel, je cherche des exemples où une limite inférieure est connue sans condition dans un modèle de calcul faible, mais dont on sait qu’elle est violée dans un modèle plus fort. De plus, la faiblesse du modèle faible devrait prendre la forme d'une abstraction , qui est certes une notion subjective. Par exemple, je ne considère pas que la restriction imposée aux circuits monotones soit une abstraction. Espérons que les deux exemples ci-dessus montrent clairement ce que je recherche.

[1] KLYUYEV, VV et NI KOKOVKIN-SHcHERBAK: sur la minimisation du nombre d'opérations arithmétiques pour la solution de systèmes d'équations algébriques linéaires. Traduction par GI TEE: Rapport technique CS 24, t4 juin, t965, département d'informatique, université de Stanford.

Un autre bel exemple du prix de l'abstraction: le codage réseau . Il est connu que dans les paramètres de multidiffusion, la relation max-flow-min-cut n’est pas une relation d’égalité (primal et dual ne correspondent pas). Cependant, les modèles traditionnels supposent que le flux est simplement transmis et non "traité" de quelque manière que ce soit. Avec le codage réseau, vous pouvez dépasser cette limite en combinant intelligemment les flux. Cet exemple a été un grand facteur de motivation pour l’étude du codage de réseau.

La programmation purement fonctionnelle est une abstraction populaire qui offre, du moins selon ses partisans, une forte augmentation du pouvoir d'expression du code, entre autres avantages. Cependant, comme il s’agit d’un modèle restrictif de la machine - en particulier, ne permettant pas une mémoire mutable - il pose la question du ralentissement asymptotique par rapport au modèle habituel (RAM).

Il y a un bon fil sur cette question ici . Les principaux plats à emporter semblent être:

1. Vous pouvez simuler une mémoire mutable avec une arborescence binaire équilibrée. Le ralentissement dans le pire des cas est donc O (log n).
2. Avec une évaluation soignée , il y a des problèmes pour lesquels c'est le mieux que vous puissiez faire.
3. Avec une évaluation paresseuse , on ne sait pas s'il y a un écart. Cependant, il existe de nombreux problèmes naturels pour lesquels aucun algorithme purement fonctionnel connu ne correspond à la complexité optimale de la RAM.

Il me semble que cette question est étonnamment fondamentale et ouverte.

Bien que votre question se concentre sur la théorie de la complexité, des choses similaires peuvent se produire dans d'autres domaines tels que la théorie des langages de programmation. Voici quelques exemples où l'abstraction rend quelque chose d'indécidable (c'est-à-dire que la limite inférieure du modèle faible est impossible, alors que le modèle fort permet d'exprimer l'algorithme):

• Dans le lambda calcul, il y a des fonctions que vous ne pouvez pas exprimer directement (par exemple, en tant que terme lambda qui bêta-réduit au résultat souhaité). Un exemple est parallèle ou (fonction de deux arguments qui renvoie celui qui se termine). Un autre exemple est une fonction qui affiche littéralement son argument (une fonction ne peut évidemment pas distinguer deux arguments bêta-équivalents). Le manque d’expression est dû à l’abstraction voulant que les termes lambda bêta-équivalents doivent être traités de manière identique.

• Dans un langage à typage statique qui ne possède qu'un polymorphisme paramétrique , tel que ML sans extension fantaisie, il est impossible d'écrire certaines fonctions - vous obtenez gratuitement des théorèmes . Par exemple, une fonction dont le type est (quel que soit le type de l'argument, renvoie un objet du même type) doit être la fonction identité ou ne pas se terminer. Le manque d’expression est dû à l’abstraction voulant que si vous ne connaissez pas le type d’une valeur, c’est opaque (vous ne pouvez que le faire circuler).$\forall\alpha, \alpha\to\alpha$

Le "prix de l'abstraction" peut également être trouvé lors de la résolution du problème du logarithme discret en cryptographie. Shoup (1997) a montré que toute approche générique (c'est-à-dire des algorithmes n'utilisant que des opérations de groupe) doit utiliser au moins opérations de groupe, oùmest la taille du groupe. Cela correspond à la complexité de l'attaque d'anniversairegénérique. Cependant,algorithmes telslecalcul deindexou l'algorithme Pohlig-Hellmanreposent sur le nombre destructure théorétique Z * n pour obteniralgorithmespeu plus rapide (au moins dansgroupes d'ordre lisse).$\Omega(\sqrt{m})$$m$$\mathbb{Z}_n^*$

Cette observation est une des raisons de la popularité de la cryptographie à courbe elliptique (par opposition à la cryptographie dans des groupes tels que ) car, essentiellement, nous ne connaissons que des approches génériques pour résoudre le problème du logarithme discret dans des groupes basés sur des courbes elliptiques.$\mathbb{Z}_n^*$

Voici un exemple d'algorithme de graphe. Étant donné un graphe orienté avec des poids non négatifs sur les arêtes, le problème des chemins goulot d'étranglement pour toutes les paires consiste à calculer, pour toutes les paires de sommets et t , le flux maximal pouvant être poussé sur un chemin donné de s à t . (Formellement, nous maximisons simplement le poids minimum d’une arête sur n’importe quel chemin de s à t . Plus formellement, nous remplaçons min et + dans la définition des plus courts chemins de toutes les paires avec max et min .)$s$$t$$s$$t$$s$$t$$\min$$+$$\max$$\min$

Soit le nombre de sommets du graphe en entrée. Ce problème était connu pour avoir besoin de Ω ( n 3 ) dans le modèle de comparaison de chemins de Karger, Koller et Phillips , tout comme le problème du chemin le plus court pour toutes les paires. (Le modèle chemin de comparaison prend en charge les algorithmes traditionnels, comme Floyd-Warshall.) Cependant, contrairement à toutes les paires de chemins les plus courts, il se trouve que toutes les paires de goulot d' étranglement chemins peuvent être résolus en moins de O ( n 2.8 ) du temps en utilisant la multiplication matricielle rapide .$n$$\Omega(n^3)$$O(n^{2.8})$

Selon une discussion dans cette question , de nombreux problèmes de géométrie informatique ont des limites inférieures dans l'arbre de décision algébrique ou les modèles d'arbre de calcul algébrique, issus de problèmes fondamentaux tels que le tri ou la distinction d'éléments . Il n’est pas difficile de trouver des articles affirmant que les limites supérieures de O ( n log n ) sur des problèmes connexes, tels que la construction des triangulations de Delaunay, sont optimales, car elles correspondent à ces limites inférieures.$\Omega(n\log n)$$O(n\log n)$

Toutefois, lorsque l'entrée est spécifiée en coordonnées cartésiennes entières (comme c'est souvent le cas, la virgule flottante convient mal à la géométrie de calcul), ces limites inférieures ne correspondent pas au modèle de calcul. Il n’est peut-être pas étonnant que les problèmes de type recherche par plage orthogonale puissent être résolus plus rapidement en utilisant des techniques adaptées du tri entier, mais même les problèmes non orthogonaux peuvent souvent avoir des algorithmes plus rapides (résolvant le problème avec précision ) fois la précision des entiers en entrée). Voir, par exemple, arXiv: 1010.1948 pour une série d’exemples.

Il existe de nombreux exemples de ce type en cryptographie, en particulier les preuves à zéro connaissance. Voir par exemple la thèse:

Boaz Barak, Techniques non cryptographiques en cryptographie, 2003.

(Incidemment, le titre de la thèse ne fournit aucune preuve de la validité de ce commentaire :)

$\Omega(n \log n)$$\Omega(n \log n)$$O(n)$algorithme de temps attendu pour la résolution de la paire de points la plus proche dans le plan, qui est une généralisation de l'unicité des éléments. Il échappe à l'arbre de décision algébrique lié en utilisant le hachage. Je l'ai trouvé dans le livre Algorithm Design de Klein et Tardos. Il existe un algorithme similaire mais plus complexe pour résoudre le même problème décrit sur le blog de RJ Lipton .

Référence:

• Richard J. Lipton, " Rabin Flips a Coin ", mars 2009,
  publié sur le blog Lost Letter de Godel et P = NP .

$k$$3$$k$$3$

$k$$\Omega(k)$

Cependant, cette abstraction est manifestement fausse: si vous pouvez transmettre quelque chose dans un réseau de communication, vous aurez un moyen de coder "quelque chose" sous forme de chaîne de bits. Et maintenant, les choses commencent à aller beaucoup mieux.

$1, 2, ..., k$$O(\log^* k)$$1, 2, ..., 10^{10^k}$$O(\log^* k)$

$O(\log^* k)$$\Omega(k)$

Un exemple qui me vient à l’esprit est le calcul du volume. Un résultat de Barany et Furedi est qu’il vous faut un nombre exponentiel de requêtes et qu’il existe un algorithme de temps polynomial randomisé de Dyer-Frieze-Kannan . L’écart représente le prix de l’abstraction et aussi l’avantage du hasard, mais je pense que la raison principale de cet écart est le prix de l’abstraction. (J'espère avoir compris la question et qu'elle va dans la bonne direction.)

Ce n'est probablement pas exactement ce que vous aviez à l'esprit. Mais dans un certain sens, l’indépendance de P vs NP par rapport aux oracles en est un exemple. Cela dit vraiment que si vous ne vous souciez que de la simulation et de l'énumération (c'est-à-dire si c'est votre "modèle" de calcul), vous ne pouvez pas séparer ces classes ni les réduire.

Un exemple algorithmique plus concret provient de la recherche de distance approximative dans le sens "inverse". Plus précisément, la plupart des problèmes de recherche de plages sont exprimés en sommes de semigroupes, et les limites inférieure / supérieure sont exprimées indépendamment de la structure de ce semigroupe (à l’exception de certaines conditions techniques peu contraignantes). Des travaux récents d' Arya, Malamatos et Mount montrent que, si vous examinez de près la structure du semigroupe (les propriétés de l'idempotence et de l'intégralité), vous pouvez alors établir des limites différentes (et plus étroites) pour la recherche de distance approximative.

Le théorème d'échantillonnage de Shannon-Nyquist propose une condition suffisante pour que les limites théoriques de l'information sur la communication. La théorie de l'échantillonnage s'articule autour d'exemples où le signal entrant a une représentation compacte / aléatoire. Les progrès récents en matière d'échantillonnage montrent que cette abstraction a peut-être un prix - que le type de mesures que nous souhaitons mesurer a généralement des représentations éparses, de sorte que ces limites ne sont pas étroites. De plus, les informations peuvent être codées de manière beaucoup plus dense qu’on ne le pensait à l’origine.

• Les codes de correction d'erreur suggèrent que certaines réévaluations de la limite de Shannon dans les paysages en réseau sujets au bruit.
• Le tout nouveau domaine de la détection en compression pousse à la reconstruction des variétés d'images que nous trouvons intéressantes au-delà de la limite de Shannon.

De nombreux problèmes intéressants soulevés par les sciences de la nature se révèlent difficiles à résoudre au sens classique du terme. Bien que cette notion soit théoriquement parfaitement valable, elle n’aide en rien le biologiste ou le physicien. Nous constatons que certains problèmes NP-durs sont des paramètres fixes traitables et souvent avec un paramètre qui est observé être lié par une petite constante dans le monde réel.

C'est-à-dire que TCS nous dit que nous ne nous attendons pas à une solution efficace au problème abstrait, mais que nous pouvons résoudre rapidement les situations qui se produisent réellement - un écart considérable.

Dans cet article, http://www.mimuw.edu.pl/~szymtor/papers/atom-turing.pdf, nous avons étudié les machines de Turing, qui ont un accès limité aux données. Ceci est formalisé comme étant invariant sous les automorphismes d'une structure relationnelle; Par exemple, dans la limite inférieure O (n log n) pour le tri, vous diriez que la machine peut traiter et stocker des nombres rationnels, mais ses transitions doivent être invariantes sous les automorphismes de (Q, <), c'est-à-dire les bijections monotones. La définition formelle est plus compliquée, afin de spécifier précisément le type de structures de données que la machine peut stocker dans sa mémoire (elle devrait être "finie"
dans un sens, mais nous permettons de stocker des structures plus compliquées que seulement des n-uplets de valeurs de données, comme les tuples non ordonnés).

Dans le document, nous avons prouvé certaines limites inférieures pour d'autres machines Turing avec "accès restreint aux données". En particulier, nous avons montré que:

• Une machine de Turing déterministe qui peut gérer des vecteurs (par exemple sur le champ de deux éléments), mais ne peut utiliser que des tests d’addition et d’égalité de vecteurs, ne peut pas déterminer en temps polynomial si une liste donnée de vecteurs est linéairement dépendante (formellement, les transitions de machine devraient être invariant sous les automorphismes de l'espace vectoriel). Ceci est opposé aux machines non déterministes, qui peuvent simplement deviner une combinaison des vecteurs qui totalise 0. Observez que l'élimination gaussienne s'exécute en temps polynomial, mais a accès aux coordonnées des vecteurs; en particulier, ses transitions ne sont pas invariantes sous les automorphismes de l'espace vectoriel.

• Dans un modèle correctement défini, les machines de Turing qui ne peuvent comparer les nombres naturels que par rapport à l'égalité (même pas <) ne peuvent pas être déterminées. Ici, nous considérons la structure relationnelle (N, =) et les machines invariantes sous ses automorphismes. Il existe une construction (similaire à celle de Cai-Furer-Immerman de la théorie des modèles finis) qui montre que, dans ce modèle, P ≠ NP. Permettre aux machines de comparer les nombres avec <leur donne suffisamment de puissance pour déterminer.

Un prix général de l'abstraction est présent dans les cadres de type boîte noire tels que la complexité de l'arbre décisionnel ou la complexité de la requête quantique. Si nous limitons l'analyse à ces modèles, nous pouvons souvent trouver de très bonnes limites pour la complexité des tâches. En fait, pour une requête quantique, nous pouvons fondamentalement résoudre la complexité des problèmes car la méthode de l'adversaire négatif fournit des limites inférieures strictes (avec un facteur de log n / loglog n: 1005.1601 ). Cela nous donne un excellent outil pour analyser la complexité des requêtes, mais il devient souvent difficile de comparer la complexité des requêtes à une complexité temps / espace plus classique de la machine turing (sauf comme limite inférieure grossière).

Voici deux exemples, tous deux liés aux modèles continu vs discret:

1. $[0,1]$$x$$y$$x<y$$x=y$$x>y$$x$$|x-y|$$y=x$

   $y$$[0,1]$$y=x$

2. La motivation pour le problème A vient du problème de la division des gâteaux sans envie . Stromquist a montré qu’aucun protocole fini (même sans limite) ne peut garantir une division du gâteau sans envie entre trois joueurs ou plus, si chaque joueur doit recevoir un seul morceau connecté.

   $i$$\alpha$$i$$x$$vi(0,x) = \alpha$

   De plus, le résultat ne concerne pas les algorithmes avec des opérations continues, telles que les procédures à couteau mobile.

Lorsqu'elle est exprimée en logique du premier ordre, toute preuve du principe du casier pour n fixé est exponentielle en longueur. Cependant, avec l'arithmétique, la preuve peut être exprimée de manière beaucoup plus concise.

Le succès des solveurs SMT provient du retrait du modèle abstrait de réduction des problèmes à la SAT, permettant ainsi à des théories plus riches de réduire considérablement le nombre de calculs nécessaires.