Théorie de la complexité lorsqu'un oracle fait partie de l'entrée

La façon la plus courante dans laquelle les oracles se produisent dans la théorie de la complexité est la suivante: un oracle fixe est mis à la disposition, par exemple, d'une machine de Turing avec certaines ressources limitées, et on étudie comment l'oracle augmente la puissance de calcul de la machine.

Il existe cependant une autre manière dont les oracles se produisent parfois: dans le cadre de l'entrée . Par exemple, supposons que je veuille étudier des algorithmes pour calculer le volume d'un polytope de haute dimension donné. Classiquement, le polytope devrait être spécifié en fournissant une liste de ses facettes ou une autre représentation explicite. Cependant, nous pouvons également poser le problème du calcul du volume d'un polytope qui est spécifié par un oracle de volume, qui prend les coordonnées d'un point dans l'espace en entrée et sort "oui" si et seulement si le point donné se trouve à l'intérieur du polytope. Ensuite, nous pouvons demander quelles ressources de calcul sont nécessaires pour calculer le volume d'un polytope spécifié de cette manière. Dans ce cas particulier, nous avons le très beau schéma d'approximation polynomiale du temps de Dyer, Frieze et Kannan et, ce qui est intéressant du point de vue de la théorie de la complexité, une preuve que le caractère aléatoire contribue de manière essentielle à ce problème, en ce qu'aucun algorithme déterministe ne peut effectuer aussi bien que l'algorithme Dyer-Frieze-Kannan.

Existe-t-il un moyen systématique d'étudier la théorie de la complexité des problèmes dans lesquels des oracles sont fournis dans le cadre de l'apport? Cela se réduit-il en quelque sorte à la théorie habituelle des classes de complexité avec des oracles? Je suppose que non, et que parce qu'il y a trop de façons différentes de fournir un oracle dans le cadre de l'entrée, chaque problème de ce type doit être traité de manière ad hoc. Cependant, je serais heureux d'avoir tort sur ce point.

Cela s'appelle la théorie de la complexité de type 2. Il y a un article de Cook, Impagliazzo et Yamakami qui le relie bien à la théorie des oracles génériques.

Cela doit être loin d'être une réponse complète, mais j'espère que cela indique certains endroits à regarder.

Les problèmes où une partie de l'entrée est donnée sous forme d'oracle sont parfois appelés problèmes avec entrée implicite . Il s'agit d'un modèle pratique, par exemple lors de l'étude de preuves probabilistes vérifiables .

Un domaine d'étude important sur les problèmes de saisie implicite est la théorie de la complexité des requêtes , où la complexité est mesurée uniquement par le nombre de requêtes vers l'oracle d'entrée, en ignorant la quantité de calcul entre les requêtes. De nombreuses classes de complexité ont leurs homologues dans la complexité des requêtes, et une séparation entre les classes de complexité dans la complexité des requêtes implique souvent une séparation Oracle entre les classes correspondantes dans la complexité de calcul.

Je ne connais pas l'étude des classes de complexité des problèmes avec entrée implicite (plutôt que des problèmes individuels) en tenant compte du coût du calcul, mais probablement certaines personnes le savent.

Le modèle où l'entrée est fournie sous forme d'oracle est étudié dans la théorie de calculabilité et l'analyse calculable. L'un des modèles qui semble proche de ce que vous voulez est le modèle TTE (Type Two Effectivity). Une bonne référence pour cela est le livre de Klaus Weihrauch " Computable Analysis ". Il parle également brièvement de la complexité dans le chapitre 7.

Le livre de Ker-I Ko " Complexité computationnelle des fonctions réelles " discute d'un autre modèle d'accès à l'oracle qui semble plus adapté à la complexité. Les problèmes de représentation des objets de type supérieur et de la méthode d'accès à l'oracle sont délicats. Voir par exemple le récent article de Stephen A. Cook et Akitoshi Kawamura " Complexity Theory for Operators in Analysis " du STOC 2010 et sa thèse de doctorat . L'un des principaux problèmes est que pour rendre le modèle raisonnable, il faut donner à la machine suffisamment de temps pour traiter les réponses de l'oracle (sinon on ne peut même pas calculer l'opérateur d'application). Pour le temps polynomial et l'espace polynomial, cela peut être fait en utilisant des polynômes d'ordre supérieur basés sur Stephen A. Cook et Bruce M. Kapron 'Une nouvelle caractérisation de la faisabilité de type 2 "FOCS 1991 et" Caractérisations des fonctions de base réalisables de type fini "STOC 1989.