Circuitos e fórmulas para clique

Question

É correto dizer que o problema de clique está em $ P $ IFF Existe uma família de circuitos booleanos $C $ para decidir clique cujos tamanhos são limitados por um polinômio?E com base em Esta questão ,Isso implica que existe um conjunto equivalente de fórmulas booleanas $ F $ para decidir clique cujos tamanhos são limitados por um polinômio?E se houver tal classe de span class="recipiente de matemática"> $ F $ , haveria derivações corretas com base em axiomas lógicos proposicionais de qualquer membro da $ f$ para o correspondente grande fórmula ingênua para clique ?

Answer 1

Tenho medo de que a resposta a todas as suas perguntas seja falsa:

• Há idiomas decididos por circuitos de tamanho constante que não são decidíveis.
• é conjeturado que $ \ mathsf {nc ^ 1} \ neq \ mathsf {p} $ .
• é conjetado que $ \ mathsf {np} \ neq \ mathsf {conp} $ .