Circuitos y fórmulas para la camarilla.

Question

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 ?

Answer 1

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} $ .