Necesita aclaración con respecto a los certificados de problemas CONP.

Question

note : Esto es no un intento de probar $ np \ neq conp $

Hay una cosa que nunca he podido digerir completamente los certificados de problemas en $ CONP $ y apreciaría mucho una aclaración definitiva de esta comunidad .

Céntrate en el problema de la suma de subconjunto ( $ ssum $ ), ahora todos sabemos que este problema está en $ NP $ desde entonces, Para aceptar la membresía del lenguaje, un Prover $ P_V $ puede emitir un certificado que un verificador $ v_r $ puede verificar En tiempo polinomial. Hasta aquí no hay problema. El complemento de este problema ( $ \ overline {subsum} $ ) está en $ CONP $ lo que significa que No sabemos si hay un certificado de sucinto (es decir, polinomial) para decidir el idioma. Si tal certificado no existe, entonces $ NP \ NEQ CONP $ y por lo tanto $ P \ NEQ NP $ . Lo que no entiendo es esto:

Si tengo (por ejemplo) un conjunto $ s $ de enteros y el número $ 0 $ Como entrada y pregunto: Demuestreme que $ \ forall s \ in s \ space \ space \ in s \ space \ space \ lnot ssum $ , es decir, $ \ nexists $ un subconjunto de $ s $ de modo que la suma de su elemento da $ 0 $ como resultado ( Esto es $ \ overline {subsum} $ , el complemento del problema de subconjunto). ¿Cómo puede existir un certificado para este problema cuya verificación está en $ P $ ? Quiero decir, necesito probarlo para todo el subconjunto, por lo que el espacio de búsqueda debe ser el POTERSET de $ s $ . Si $ | s |= n $ luego $ \ mathcal {| p (s) |}= 2 ^ n $ < / span>. Entonces, si el Prover, por ejemplo, produce un $ 2 ^ {n / 3} $ certificado, esto significa que lo dejo sistemáticamente $ 2 ^ {\ frac {2} {3} N} $ subconjuntos. Lo que no entiendo completamente y para el cual necesito una aclaración es por qué este argumento no se acepta como evidencia de que $ np $ no está cerrado bajo complemento.

Answer 1

La prueba hace que Bot necesita ser un subconjunto.Puede ser otro indicador que el conjunto dado tenga cierta estenosis que le impida ser una instancia positiva del problema de los subsetters.Un buen ejemplo con un certificado no trivial es la programación lineal.Los programas lineales admiten un certificado positivo y negativo (para la pregunta de si el óptimo puede ser más pequeño / mayor que un valor k).La instancia positiva es, por supuesto, una asignación de la variable.Sin embargo, el negativo es dado por Faraks Lemma y la dualidad débil.

Un buen ejercicio para usted es buscar programas lineales, dualidad débil y Farkas Lemma :)