Pourquoi utiliser les langages dans la théorie de la complexité

Je commence tout juste à entrer dans la théorie du calcul, qui étudie ce qui peut être calculé, à quelle vitesse, en utilisant la quantité de mémoire et avec quel modèle de calcul.

J'ai une question assez basique, mais j'espère vraiment que certains d'entre vous pourront m'aider à comprendre le concept derrière:

Pourquoi tout est-il centré sur la notion et la définition des LANGUES (c'est-à-dire les langues régulières et les langues sans contexte)? Et comment relient-ils et décrivent-ils la complexité d'un algorithme et les modèles de calcul possibles pour les résoudre?

J'ai lu ce genre de questions connexes:

• /cstheory/14811/what-is-the-enlightenment-im-supposed-to-attain-after-studying-finite-automata
• /cstheory/8539/how-practical-is-automata-theory

mais je n'ai toujours pas de réponse à mes doutes, car ils fournissent une justification pratique de la raison pour laquelle ils sont importants (ce que je comprends), mais ne m'aident pas à comprendre pourquoi la théorie de la complexité est basée sur eux.

C'est parce que les langues sont la meilleure (seule?) Façon dont nous ayons de formaliser le concept de «problème».

Un algorithme (Turing Machine) a des performances, que nous exprimons via la complexité big-O. Un problème (langue) appartient à une classe de complexité. Celles-ci sont généralement définies par l'existence: s'il existe une machine acceptant un langage qui s'exécute dans des performances données (espace ou temps), alors le langage appartient à la classe de complexité correspondante.$L$

$10^6$$10^9$$10^{12}$

La seconde est que les langues ne sont qu'une belle abstraction pour les données. Vous avez besoin de quelque chose que vous pouvez faire des preuves, quelque chose que vous pouvez modéliser formellement. L'encodage de vos entrées et sorties sous forme de chaîne signifie que vous n'avez plus affaire à des bits en mémoire, mais à des objets mathématiques aux propriétés spécifiques. Vous pouvez raisonner à leur sujet et prouver des preuves à leur sujet dans un sens formel et très simple.

$k$

Je suppose que voici mon défi pour vous: trouver un moyen de décrire mathématiquement des problèmes qui ne sont pas des langues. Je ne sais pas si les langues sont spéciales, mais je pense que c'est l'outil le plus simple que nous ayons, le plus facile à gérer.

Il y a deux réponses de base à votre question:

1. La théorie de la complexité ne se limite pas aux langages, par exemple les classes de fonctions, la complexité arithmétique et les sous-domaines d'algorithmes d'approximation et d'inapproximabilité.

2. Raisons historiques: l'un des articles de base de la théorie de la calculabilité était la discussion du problème d'Entscheidungs ​​(une forme du problème d'arrêt) de Hilbert.

Malheureusement, je ne connais pas grand-chose à ce dernier, mais permettez-moi de développer le premier.

Complexité au-delà des langues

$L$$M$$f_M$$x \in M$$f_M(x) \in L$.

La complexité des circuits arithmétiques (ou théorie de la complexité algébrique ) traite de la complexité du calcul de divers polynômes. Les classes de complexité importantes ici sont VP et VNP, et la théorie de la complexité géométrique est un projet important qui tente de séparer VP et VNP (et plus tard P et NP) en utilisant la géométrie algébrique et la théorie de la représentation.

Un autre exemple important de complexité algébrique est la multiplication matricielle rapide. Ici, la question fondamentale est de savoir à quelle vitesse pouvons-nous multiplier deux matrices ? Des questions similaires demandent à quelle vitesse nous pouvons multiplier des entiers, à quelle vitesse pouvons-nous tester des entiers pour la primauté (c'est un problème de décision!) Et à quelle vitesse pouvons-nous factoriser des entiers.

L'optimisation convexe traite des problèmes d'optimisation qui peuvent être résolus (ou presque résolus) efficacement. Des exemples sont la programmation linéaire et la programmation semi-définie, qui ont toutes deux des algorithmes efficaces. Ici, nous nous intéressons à la fois à l'optimum et à la solution optimale elle-même. Puisqu'il y a souvent plus d'une solution optimale, le calcul d'une solution optimale n'est pas bien représenté comme un problème de décision.

$\ln n$

Regardons cette question du point de vue de la théorie des catégories. Les problèmes de décision (ou langues) correspondraient alors aux objets d'une catégorie, et les réductions admises entre deux problèmes correspondraient aux morphismes (flèches) d'une catégorie.

Parler des langues présente l'avantage que l'équivalence des langues est bien définie (notamment par l'égalité d'extension). Deux problèmes indépendants peuvent conduire au même langage, et nous sommes alors autorisés à les considérer comme équivalents. Si nous voulons plutôt parler de problèmes isomorphes, nous devons définir les morphismes autorisés entre deux problèmes. Mais les morphismes autorisés dépendent de la classe de complexité réelle considérée, ce qui rend cette approche moins appropriée pour comparer différentes classes de complexité.

La notion de problèmes isomorphes sera normalement plus grossière que la notion de langues équivalentes, c'est-à-dire que deux problèmes peuvent être isomorphes, même si leurs langues associées ne sont pas équivalentes. Ce qui est pire, c'est qu'il existe souvent différentes notions raisonnables pour les morphismes autorisés, qui ne s'accordent qu'en ce qui concerne les isomorphismes autorisés. Se concentrer sur les langues permet de reporter ces problèmes jusqu'à ce que nous ayons envie de parler de différentes notions raisonnables de réduction (comme la réduction de Karp contre la réduction de Cook).