Approximate counting in bounded arithmetic (Q5422312): Difference between revisions

@@ Property / OpenAlex ID @@
+W2125894854
@@ Property / OpenAlex ID: W2125894854 / rank @@
+Normal rank
@@ Property / cites work @@
+A new proof of the weak pigeonhole principle
@@ Property / cites work: A new proof of the weak pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+Provability of the pigeonhole principle and the existence of infinitely many primes
+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 @@
+Relating the bounded arithmetic and polynomial time hierarchies
+Normal rank
@@ Property / cites work @@
+Q3794177
@@ Property / cites work: Q3794177 / rank @@
+Normal rank
@@ Property / cites work @@
+A uniform approach to define complexity classes
@@ Property / cites work: A uniform approach to define complexity classes / rank @@
+Normal rank
@@ Property / cites work @@
+Q3803111
@@ Property / cites work: Q3803111 / rank @@
+Normal rank
@@ Property / cites work @@
+Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
+Normal rank
@@ Property / cites work @@
+Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
+Normal rank
@@ Property / cites work @@
+The strength of sharply bounded induction
@@ Property / cites work: The strength of sharply bounded induction / rank @@
+Normal rank
@@ Property / cites work @@
+Dual weak pigeonhole principle, Boolean complexity, and derandomization
+Normal rank
@@ Property / cites work @@
+Complexity classes without machines: on complete languages for UP
+Normal rank
@@ Property / cites work @@
+Q5286672
@@ Property / cites work: Q5286672 / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity of Probabilistic Turing Machines
+Normal rank
@@ Property / cites work @@
+Q4671210
@@ Property / cites work: Q4671210 / rank @@
+Normal rank
@@ Property / cites work @@
+Structures interpretable in models of bounded arithmetic
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+BPP and the polynomial hierarchy
@@ Property / cites work: BPP and the polynomial hierarchy / rank @@
+Normal rank