Witnessing functions in bounded arithmetic and search problems (Q4227882): Difference between revisions

@@ Property / OpenAlex ID @@
+W2056827464
@@ Property / OpenAlex ID: W2056827464 / rank @@
+Normal rank
@@ Property / cites work @@
+On the scheme of induction for bounded arithmetic formulas
+Normal rank
@@ Property / cites work @@
+\(\Sigma_ 1^ 1\)-formulae on finite structures
@@ Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank @@
+Normal rank
@@ Property / cites work @@
+An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
+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 @@
+Quantified propositional calculi and fragments of bounded arithmetic
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+Exponential lower bounds for the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Provability of the pigeonhole principle and the existence of infinitely many primes
+Normal rank