Muchos problemas de optimización combinatoria suelen considerarse intratables de resolver exacta o aproximadamente. Un ejemplo de tal problema es , que -bajo suposiciones estándar en teoría de complejidad- no puede resolverse en tiempo subexponencial o aproximarse eficientemente dentro de un factor polinomial. Sin embargo, demostramos que si un algoritmo puede consultar priors gaussianos informativos de un experto () veces, entonces una clase de problemas de optimización combinatoria puede resolverse eficientemente hasta un factor multiplicativo , donde es una constante arbitraria. En este artículo, presentamos la prueba de nuestras afirmaciones y mostramos resultados numéricos para respaldarlas. Nuestros métodos pueden arrojar nueva luz sobre cómo abordar problemas de optimización en dominios donde ni siquiera la aproximación del problema es factible. Además, los resultados pueden ayudar a los investigadores a comprender las estructuras de estos problemas (¡o si estos problemas tienen alguna estructura en absoluto!). Si bien los métodos propuestos pueden utilizarse para aproximar problemas combinatorios en NPO, señalamos que el alcance de los problemas resolubles podría incluir problemas que son demostrablemente intratables (problemas en EXPTIME).