Schaltungen und Formeln für Clique

Question

ist es richtig zu sagen, dass das Clique-Problem in $ P $ IFF gibt, die eine Familie von booleschen Kreisläufen vorhanden sind $C $ , um Clique zu entscheiden, deren Größen von einem Polynom begrenzt sind?Und basierend auf Diese Frage ,Bedeutet das, dass es ein äquivalentes Satz von booleschen Formeln gibt $ F $ , um Clique zu entscheiden, deren Größen von einem Polynom begrenzt sind?Und wenn es einen solchen $ F $ gibt, würde es die richtigen Ableitungen auf der Grundlage von Soll-Logik-Axioms von einem Mitglied von $ F$ zum entsprechenden große naive Formel für Clique ?

Answer 1

Ich fürchte, dass die Antwort auf alle Ihre Fragen falsch ist:

• Es gibt Sprachen, die von konstanten Größenschaltungen entschieden werden, die nicht entschieden sind.
• es ist vermutet, dass $ \ mathsf {nc ^ 1} \ neq \ mathsf {p} $ .
• es ist übertragbar, dass $ \ mathsf {np} \ neq \ mathsf {conp} $ .