Postselección en teoría de la complejidad geométrica

Contexto: según tengo entendido, en la teoría de la complejidad geométrica, la existencia de obstrucciones sirve como un certificado de prueba, por así decirlo, de la inexistencia de un circuito computacional eficiente para la función explícita y difícil en el problema del límite inferior en consideración. Ahora hay algunas otras suposiciones para las obstrucciones que deben ser cortas, fáciles de verificar y fáciles de construir.

Pregunta: Mi pregunta es decir que tengo un problema que supongo que tiene solución en el tiempo polinómico. Entonces, ¿cómo puedo demostrar que no existe una obstrucción para este problema, es decir, si no existen obstrucciones, entonces el problema se puede calcular de manera eficiente y, de hecho, es en tiempo polinómico.

Enfoque: creo, y puedo estar equivocado en esta afirmación, que mostrar que no existen obstrucciones puede ser equivalente a la reducción estándar de los problemas de NP a otros problemas cuya complejidad aún se desconoce, en la prueba de que ellos mismos están en NP. Entonces, en ese caso, uno puede, si es posible, demostrar que existen obstrucciones cuando se trata de reducir un problema de NP al problema en consideración, de esa manera, la reducción es intratable. Además, ¿qué papel juega la postelección en todo esto? ¿Es posible simplemente posteleccionar en la inexistencia de obstrucciones? Gracias y perdón por la falta de declaraciones precisas en mi enfoque y preguntas.

Solo otro ejemplo, considere un problema X que sabemos que está en P. Ahora digamos que no sabíamos que ese problema se puede resolver en tiempo polinómico, entonces es posible que uno pueda hacer la siguiente afirmación:

Como no existen obstrucciones en el cálculo de X , podemos decir que está en la clase P

A partir de ahí, el problema es que el descubrimiento fácil (computacionalmente) de esas obstrucciones, si existe una, demostraría que X no está en tiempo polinomial. Sin embargo, ir en sentido contrario, es decir, descubrir que no existen obstrucciones es una tarea difícil.

$P$

A los fines de esta respuesta, podemos dividir el programa Mulmuley-Sohoni GCT en dos pasos:

1. $perm$$det$$V_{perm}$$V_{det}$$V_{perm} \subseteq V_{det}$$perm$$p$$det$

2. $V_{perm} \not\subseteq V_{det}$

Tenga en cuenta que la implicación en (2) solo va en una dirección (la existencia de obstrucción no implica la inclusión de variedades), por lo que es posible que la no sea una proyección de y, sin embargo, no existan obstrucciones teóricas de representación. Entonces, en este caso, solo probar que no existen obstrucciones no es suficiente para demostrar que la es fácil. Por otro lado, en (1) la inclusión de variedades algebraicas es tanto necesaria como suficiente para la inclusión de clases de complejidad.$perm$$p$$det$$perm$

[En lo anterior, por supuesto, se han omitido muchos detalles: la dependencia del tamaño de entrada, cómo hablar sobre la clase de complejidad lugar de , el hecho de que la inclusión de variedades es equivalente a es aproximable por las proyecciones de , ... Pero la esencia sigue siendo correcta.]$P$$det$$perm$$p$$det$

También me gusta pensar de esta manera, y lo relaciono con la conjetura . Se menciona allí o allí (me está costando encontrar páginas sobre esta conjetura, ya que solo puedo referirme a ella con símbolos matemáticos que a Google no le gustan).$P=NP\cap co-NP$

Un problema está en NP cuando puede dar un certificado para una respuesta "Verdadera" (ejemplo: un ciclo hamiltoniano para el problema TSP o una asignación válida para el problema SAT). Es en co-NP cuando puede dar un certificado para una respuesta "Falsa" (ejemplo: una "prueba" de que la fórmula SAT no es satisfactoria, un corte incorrecto en un gráfico que impide la existencia de un ciclo hamiltoniano, etc. ..)

En realidad, esas pueden ser las "obstrucciones" a las que también puede referirse. Y esta conjetura se trata de decir: un problema que está en NP es polinómico cuando sé cuáles son las obstrucciones.

Ahora, las "obstrucciones" pueden tomar muchas formas diferentes. Para el problema de coincidencia (que es polinomial) puede ser una partición del gráfico (consulte la caracterización de gráficos de Tutte que admite una coincidencia perfecta ), o puede ser el certificado otorgado por Farkas's Lemma para programación lineal (y problemas de gráficos que pueden reducirse lo). En realidad, puede ser una gran cantidad de cosas, por lo que generalmente "uso" esta conjetura en una dirección: cuando no puedo encontrar obstrucciones, no deduzco que mi problema es NP-Hard. Algunas obstrucciones son realmente difíciles de encontrar ... Pero cuando tengo un algoritmo polinómico complicado para un problema, a veces estoy convencido de que "debe haber un conjunto comprensible de obstrucciones, que sería más fácil de entender que el algoritmo complicado".

Bueno ... mis dos centavos :-)

Nathann