Circuitos y fórmulas para la camarilla.
-
29-09-2020 - |
Pregunta
es correcto decir que el problema de la clama está en $ P $ IFF Existe una familia de circuitos booleanos $C $ para decidir la clique cuyos tamaños están limitados por un polinomio?Y basado en esta pregunta ,¿Eso implica que existe un conjunto equivalente de fórmulas booleanas $ f $ para decidir la camarilla cuyos tamaños están limitados por un polinomio?Y si hay un $ f $ , ¿habría derivaciones correctas basadas en axiomas lógicos proposicionales de cualquier miembro de $ f$ a los correspondientes Fórmula de gran ingenua para la clique ?
Solución
Me temo que la respuesta a todas sus preguntas es falsa:
- Hay idiomas decididos por circuitos de tamaño constante que no son decidibles.
- Se conjeture ese $ \ mathsf {nc ^ 1} \ neq \ mathsf {p} $ .
- Se conjeture ese $ \ mathsf {np} \ neq \ mathsf {CONP} $ .
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange