Casi siempre casi correcto

11

Estoy buscando una clase de complejidad que se relacione con APX como BPP se relaciona con P. Ya he hecho la misma pregunta aquí , pero tal vez TCS sería una ubicación más fructífera para las respuestas.

La razón de la pregunta es que, en problemas prácticos, a menudo es necesario encontrar respuestas aproximadas (por lo tanto, APX) con una confianza suficientemente alta (por lo tanto, BPP), lo que haría que la clase de problemas con algoritmos de aproximación probabilística acotada sea un modelo potencialmente útil de lo que es computable en práctica.

Un posible candidato de dicha clase sería : problemas que admiten soluciones aproximadas con subrutinas probabilísticas limitadas; sin embargo, no estoy seguro de que esa clase sea la configuración adecuada para las aproximaciones de clase probabilísticamente computables.APXBPP

Tanto BPP como APX han sido ampliamente estudiados. ¿Es ese el caso de , o la clase que sea la mejor para capturar los problemas anteriores?APXBPP

cc.complexity-theory approximation-hardness Miguel
fuente
BPP y P son clases de problemas de decisión. Tal vez debería preguntar primero cuál es la clase de función / búsqueda correspondiente a BPP antes de pasar a la aproximación, creo que si tenemos la clase de función / búsqueda, entonces la definición de su versión de aproximación no debería ser difícil.
Kaveh
1
Creo que lo que está buscando es la versión de optimización del aprendizaje PAC (Probablemente Aproximadamente Correcto). Mientras que la teoría del aprendizaje PAC trata específicamente (al azar, con una alta probabilidad de corrección) de funciones de aprendizaje para describir datos, como en el aprendizaje automático, usted está preguntando acerca de los problemas de optimización. Aún así, tal vez la literatura de aprendizaje de PAC es un buen lugar para comenzar a buscar ...
Joshua Grochow
3
En lugar de la notación de oráculo, lo que está describiendo está más cerca del operador de BP. El operador BP se define en clases de complejidad de problemas de decisión. Debería ser fácil extender la definición a problemas prometedores y definir una versión de problema prometedor de su clase de complejidad de esa manera. Definir una versión para problemas de optimización puede ser más complicado.
Sasho Nikolov

Respuestas:

1

Para cualquier función objetivo dada, deje que BotL (el mejor de la lista) sea el algoritmo que evalúa la función objetivo en un conjunto de entradas y devuelve una entrada de esa lista que tuvo una salida máxima (de entre esas entradas), con vínculos roto arbitrariamente Dado que APX solo incluye problemas
cuya función objetivo se puede calcular en tiempo polinomial determinista, BotL se puede implementar de manera determinista en tiempo polinomial.Además, el valor devuelto por BotL
es al menos tan bueno como cualquiera de las entradas en el mínimo en el que se evaluó BotL.En particular,
si alguna de las entradas en esa lista es lo suficientemente buena, entonces la salida de BotL será lo suficientemente buena.
Por lo tanto, ejecutar BotL en las salidas de un número suficientemente grande de ejecuciones independientes de un algoritmo base puede amplificar la probabilidad de éxito de 1 / poli a 1- (1 / (2 ^ poli)).

Como consecuencia del párrafo anterior, el
nivel de confianza preciso esencialmente no afecta a la clase resultante.
(Esta situación es muy análoga a RP ).

No pude encontrar nada sobre eso en el complejo zoológico, aunque
podría haber habido charlas al respecto en el taller mencionado en este documento .


fuente
1
OP solicita el nombre de la clase de problemas que tienen algoritmos de aproximación aleatoria de factor constante. Usted está diciendo (creo) que la probabilidad de éxito de tales algoritmos puede amplificarse. ¿No veo cómo responde esto a la pregunta?
Sasho Nikolov
No veo esa pregunta en el OP. Michael pregunta si la clase "ha sido ampliamente estudiada". Es cierto que no tenía mucho que decir al respecto, pero sí (al menos traté de) abordar un malentendido acerca de lo que sería esa clase.
No hay tal malentendido en la pregunta.
Sasho Nikolov
Derecha. El malentendido está en "Un posible candidato de tal clase sería ... aproximaciones probabilísticamente computables". párrafo, que está en la publicación pero no en la pregunta.
1
Con las aclaraciones, todavía es mi opinión que su respuesta no está corrigiendo un malentendido en el OP, sino que solo da un hecho arbitrario sobre aproximaciones aleatorias.
Sasho Nikolov