A Tight Karp-Lipton Collapse Result in Bounded Arithmetic (Q3540180): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W1503766551
@@ Property / OpenAlex ID: W1503766551 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4039803
@@ Property / cites work: Q4039803 / rank @@
+Normal rank
@@ Property / cites work @@
+Bounded queries to SAT and the Boolean hierarchy
@@ Property / cites work: Bounded queries to SAT and the Boolean hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Q4418680
@@ Property / cites work: Q4418680 / rank @@
+Normal rank
@@ Property / cites work @@
+\(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
+Normal rank
@@ Property / cites work @@
+Competing provers yield improved Karp-Lipton collapse results
+Normal rank
@@ Property / cites work @@
+The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
+Normal rank
@@ Property / cites work @@
+Q4133141
@@ Property / cites work: Q4133141 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5465359
@@ Property / cites work: Q5465359 / rank @@
+Normal rank
@@ Property / cites work @@
+Consequences of the provability of <i>NP</i> ⊆ <i>P</i>/<i>poly</i>
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+Approximate counting in bounded arithmetic
@@ Property / cites work: Approximate counting in bounded arithmetic / rank @@
+Normal rank
@@ Property / cites work @@
+The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+New Collapse Consequences of NP Having Small Circuits
+Normal rank
@@ Property / cites work @@
+Q4856172
@@ Property / cites work: Q4856172 / rank @@
+Normal rank
@@ Property / cites work @@
+Propositional proof systems, the consistency of first order theories and the complexity of computations
+Normal rank
@@ Property / cites work @@
+Bounded arithmetic and the polynomial hierarchy
@@ Property / cites work: Bounded arithmetic and the polynomial hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+On an optimal propositional proof system and the structure of easy subsets of TAUT.
+Normal rank
@@ Property / cites work @@
+Notes on polynomially bounded arithmetic
@@ Property / cites work: Notes on polynomially bounded arithmetic / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:3540180