Teoría de la complejidad cuando un oráculo es parte de la entrada

La forma más común en que ocurren los oráculos en la teoría de la complejidad es la siguiente: se pone a disposición un oráculo fijo , por ejemplo, para una máquina de Turing con ciertos recursos limitados, y uno estudia cómo el oráculo aumenta el poder computacional de la máquina.

Sin embargo, a veces se producen oráculos: como parte de la entrada . Por ejemplo, supongamos que quiero estudiar algoritmos para calcular el volumen de un politopo de alta dimensión dado. Clásicamente, el politopo necesitaría especificarse proporcionando una lista de sus facetas o alguna otra representación explícita. Sin embargo, también podemos plantear el problema de calcular el volumen de un politopo especificado por un oráculo de volumen , que toma las coordenadas de un punto en el espacio como entrada y emite "sí" si y solo si el punto dado se encuentra dentro del politopo. Luego podemos preguntar qué recursos computacionales son necesarios para calcular el volumen de un politopo que se especifica de esta manera. En este caso particular, tenemos el esquema de aproximación de tiempo polinómico muy agradable de Dyer, Frieze y Kannan y, curiosamente desde el punto de vista de la teoría de la complejidad, una prueba de que la aleatoriedad ayuda de una manera esencial para este problema, ya que ningún algoritmo determinista puede funcionar tan bien como el algoritmo Dyer-Frieze-Kannan.

¿Existe una forma sistemática de estudiar la teoría de la complejidad de los problemas en los que se proporcionan oráculos como parte de la entrada? ¿De alguna manera se reduce a la teoría habitual de las clases de complejidad con oráculos? Mi conjetura es que no, y debido a que hay muchas maneras diferentes en que un oráculo podría ser suministrado como parte de la entrada, cada problema de este tipo debe ser manejado de manera ad hoc. Sin embargo, estaría feliz de que me demuestren que estoy equivocado en este punto.

Se llama teoría de la complejidad tipo 2. Hay un artículo de Cook, Impagliazzo y Yamakami que lo vincula muy bien con la teoría de los oráculos genéricos.

Esto debe estar lejos de ser una respuesta completa, pero es de esperar que señale algunos lugares para mirar.

Los problemas en los que parte de la entrada se da como un oráculo a veces se denominan problemas con entrada implícita . Es un modelo conveniente, por ejemplo, cuando se estudian pruebas probabilísticamente comprobables .

Un área importante de estudio sobre los problemas con la entrada implícita es la teoría de la complejidad de la consulta , donde la complejidad se mide únicamente por el número de consultas al oráculo de entrada, ignorando la cantidad de cómputo entre consultas. Muchas clases de complejidad tienen sus contrapartes en la complejidad de la consulta, y una separación entre las clases de complejidad en la complejidad de la consulta a menudo implica una separación de oráculo entre las clases correspondientes en la complejidad computacional.

No conozco el estudio de las clases de problemas de complejidad con entrada implícita (en lugar de problemas individuales) teniendo en cuenta el costo de la computación, pero probablemente algunas personas lo sepan.

El modelo donde se proporciona la entrada como un oráculo se estudia en la teoría de la computabilidad y el análisis computable. Uno de los modelos que parecen cercanos a lo que quieres es el modelo TTE (Tipo Dos Efectividad). Una buena referencia para ello es el libro de Klaus Weihrauch " Análisis computable ". También habla brevemente sobre la complejidad en el capítulo 7.

El libro de Ker-I Ko " Complejidad computacional de las funciones reales " analiza otro modelo de acceso al oráculo que parece más adecuado para la complejidad. Los problemas sobre la representación de objetos de tipo superior y el método para acceder al oráculo son asuntos delicados. Véase, por ejemplo, el reciente artículo de Stephen A. Cook y Akitoshi Kawamura " Teoría de la complejidad para operadores en análisis " de STOC 2010 y su tesis doctoral . Uno de los principales problemas es que para que el modelo sea razonable, es necesario darle a la máquina el tiempo suficiente para procesar las respuestas del oráculo (de lo contrario, ni siquiera se puede calcular el operador de la aplicación). Para el tiempo polinómico y el espacio polinómico se puede hacer usando polinomios de orden superior basados ​​en Stephen A. Cook y Bruce M. Kapron 'Una nueva caracterización de la viabilidad de tipo 2 "FOCS 1991 y" Caracterizaciones de los funcionales básicos factibles de tipo finito "STOC 1989.