Y a-t-il des problèmes sans algorithmes efficaces, où les théorèmes d'existence ont prouvé que de tels algorithmes doivent exister?

22

Y a-t-il des problèmes dans CS où aucun algorithme efficace n'est connu, malgré l'existence de théorèmes prouvant que de tels algorithmes efficaces doivent exister?

Comment s'appellent ces problèmes? Où puis-je en savoir plus?

ds.algorithms reference-request terminology z5h
la source
4
Je pense que cela est pertinent: en.wikipedia.org/wiki/Minor_(graph_theory)#Algorithms
Philip White
3
Quelle est ta question? Dans le titre dit "solutions", mais dans le contenu vous écrivez "algorithmes".
Marcos Villagra
6
Je pense que ce serait mieux si vous posez des problèmes intéressants / naturels , sinon il est facile de définir de tels problèmes: prenez n'importe quelle déclaration mathématique qui n'est pas connue pour être vraie ou fausse, faites la sortie du problème 1 (indépendante de l'entrée) si elle est vrai et 0 s'il est faux. Il y a deux algorithmes très simples que l'un d'eux résout ce problème, mais qui décide essentiellement de prouver / réfuter l'énoncé mathématique, nous ne savons donc pas lequel le résout.
Kaveh

Réponses:

9

À titre d'exemple, Shelby Kimmel utilise la méthode de l'adversaire dans cet article pour montrer qu'il doit exister algorithme de requête pour un certain problème pour lequel nous ne connaissons pas de solution de requête constante. Elle le fait de manière particulièrement astucieuse en trouvant la complexité de requête du problème composé avec elle-même fois, puis en trouvant la complexité de requête de la fonction compostée, et en notant que la complexité de requête de la fonction d'origine est de l'ordre .O(1)réQQ1ré

Artem Kaznatcheev
la source
12

Bien sûr, il existe de nombreux exemples, du moins dans l'esprit de votre question.

On obtient souvent un tel résultat de la méthode probabiliste . Par exemple, un article que j'aime et qui pose problème est la reconstruction de graphiques dans le modèle additif . Ici, les auteurs montrent qu'il existe un ensemble de requêtes qui apprendront (de manière optimale) le graphe cible. Compte tenu de cet ensemble, l'algorithme est efficace. Cependant, ils utilisent la méthode probabiliste pour montrer l'existence de ce petit ensemble (pour chaque taille de problème) qui fonctionnera sur toutes les entrées, mais ne le construisent pas explicitement. Donc, le mieux qu'ils peuvent faire est simplement une recherche par force brute à travers une famille exponentielle de requêtes car elles n'ont pas de construction explicite.O(rén)

Lev Reyzin
la source
2

Non, vous pouvez toujours utiliser l'algorithme le plus rapide et le plus court pour tous les problèmes bien définis . ;)

Marcus Ritt
la source
Je n'étais pas totalement sérieux, mais observez que la construction de Hutter prouve en fait l'exactitude de l'algorithme. Pourquoi pensez-vous que cela ne répond pas à la question?
Marcus Ritt
4
@Ross Snider: bien sûr, les langages indécidables échappent au résultat de Hutter: après tout, il donne un algorithme! Cependant, contrairement à la recherche Levin, qui exige que les instances problématiques aient des certificats vérifiables (comme les problèmes de recherche NP), la recherche de Hutter n'en a pas. Elle exige simplement que le problème soit énoncé dans un langage formel, qui peut servir de base à la recherche exhaustive de preuves [qu'une certaine MT résout en fait le problème spécifié]. De plus, Hutter / Levin ne nous donne pas de preuves d'existence d'algorithmes efficaces pour un problème, sauf si nous savons déjà que le problème a un tel algorithme.
Joshua Grochow
1
@Joshua J'ai évoqué des langues indécidables comme exemple de quelque chose que la recherche de Hutter / Levin ne pouvait pas décider (j'ai essayé de choisir quelque chose d'évident) mais qui reste "bien défini"; c'est un argument contre la réclamation faite dans le titre de l'article. Bien sûr, j'ai pris soin d'admettre que je n'avais pas lu le contenu, ce que je vais devoir faire maintenant.
Ross Snider
1
Cet algorithme est-il le contenu de calcul de l'équivalence des mathématiques constructives et classiques sur des énoncés qui existent tous?
Neel Krishnaswami
1
@Neel Kirshnaswami: C'est difficile à dire, car je ne savais pas qu'il y avait une telle équivalence! Pouvez-vous donner un pointeur?
Joshua Grochow
1

Edit: La réponse ci-dessous est en train de régner sur l'existence de solutions à un problème de calcul donné, et non sur l'existence d'algorithmes. Au départ, j'ai mal interprété la question.

Répondre

Il existe une classe de complexité qui capture ce type de problèmes de calcul. Il est connu sous le nom de TFNP . Il a été défini dans cet article:

Nimrod Megiddo et Christos Papadimitriou. Sur les fonctions totales, les théorèmes d'existence et la complexité de calcul . Informatique théorique 81 (2): 317-324.

Vous trouverez ici des problèmes comme le Triangle Trichromatique, pour lesquels l'existence d'une solution est garantie par le lemme de Sperner (voir l'article pour la définition de ce problème).

Vous avez également le document suivant:

Christos Papadimitriou. Sur la complexité de l'argument de la parité et d'autres preuves d'existence inefficaces . Journal of Computer and Systems Science 48 (3), 1990.

Dans cet article, vous trouverez:

  • n
  • Equilibre des jeux à 2 joueurs.
  • Trouvez un deuxième chemin hamiltonien sur un graphique.

Le document contient de nombreux exemples de ce type de problèmes. Je recommande donc d'y jeter un œil.

Marcos Villagra
la source
2
La question ne porte pas sur les problèmes avec les solutions prouvées existantes pour leurs versions de décision, mais sur les problèmes avec l'existence prouvée d'algorithmes efficaces. Ce sont des choses différentes. Je reconnais qu'à première vue le titre peut induire en erreur. Cependant, seulement à première vue.
Oleksandr Bondarenko
oui, je suis d'accord aussi. Mais j'ai été totalement induit en erreur par la question. Maintenant, dans ce cas, la réponse est trompeuse. Que fais-je? Dois-je supprimer de question? Ou modifier et mettre un avertissement sur ce qu'est exactement la réponse?
Marcos Villagra
Il n'y a pas de politique de suppression des réponses, vous pouvez toujours faire ce que vous jugez approprié. Personnellement, je pense que c'est bien de laisser votre réponse ici. Vous pouvez indiquer à quelle question vous répondez exactement.
Hsien-Chih Chang 張顯 之