Circuiti e formule per clique

Question

è corretto dire che il problema della clique è in $ P $ IFS esiste una famiglia di circuiti booleani $C $ per decidere Clique le cui taglie sono delimitate da un polinomio?E basato su Questa domanda ,Questo implica che esiste un insieme equivalente di formule booleane $ f $ per decidere Clique le cui taglie sono delimitate da un polinomio?E se c'è una tale class class="container di matematica"> $ f $ , ci saranno derivazioni corrette sulla base degli assiomi proposizionali di logica da qualsiasi membro della $ f$ al corrispondente grande formula ingenua per clique ?

Answer 1

Ho paura che la risposta a tutte le tue domande sia falsa:

.
• Ci sono lingue decise da circuiti di dimensione costante che non sono decidabili.
• è congetturato che $ \ mathsf {nc ^ 1} \ neq \ mathsf {p} $ .
• è congetturato che $ \ mathsf {np} \ neq \ mathsf {conp} $ .