Some consequences of cryptographical conjectures for \(S_2^1\) and EF (Q1383164): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1006/inco.1997.2674
+Normal rank
@@ Property / OpenAlex ID @@
+W2068363706
@@ Property / OpenAlex ID: W2068363706 / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q106785148
@@ Property / Wikidata QID: Q106785148 / rank @@
+Normal rank
@@ Property / cites work @@
+RSA and Rabin Functions: Certain Parts are as Hard as the Whole
+Normal rank
@@ Property / cites work @@
+Lower bounds for cutting planes proofs with small coefficients
+Normal rank
@@ Property / cites work @@
+Q3794177
@@ Property / cites work: Q3794177 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228469
@@ Property / cites work: Q4228469 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4133141
@@ Property / cites work: Q4133141 / rank @@
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+Fragments of Bounded Arithmetic and Bounded Query Classes
+Normal rank
@@ Property / cites work @@
+Lower bounds to the size of constant-depth propositional proofs
+Normal rank
@@ Property / cites work @@
+Q4856172
@@ Property / cites work: Q4856172 / rank @@
+Normal rank
@@ Property / cites work @@
+Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
+Normal rank
@@ Property / cites work @@
+Interpolation by a Game
@@ Property / cites work: Interpolation by a Game / rank @@
+Normal rank
@@ Property / cites work @@
+Q4395611
@@ Property / cites work: Q4395611 / 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 @@
+Quantified propositional calculi and fragments of bounded arithmetic
+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 @@
+Q4744264
@@ Property / cites work: Q4744264 / rank @@
+Normal rank
@@ Property / cites work @@
+A lower bound for the complexity of Craig's interpolants in sentential logic
+Normal rank
@@ Property / cites work @@
+Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
+Normal rank
@@ Property / cites work @@
+Q4298260
@@ Property / cites work: Q4298260 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3689182
@@ Property / cites work: Q3689182 / rank @@
+Normal rank
@@ Property / cites work @@
+Provability of the pigeonhole principle and the existence of infinitely many primes
+Normal rank
@@ Property / cites work @@
+Every Prime Has a Succinct Certificate
@@ Property / cites work: Every Prime Has a Succinct Certificate / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for resolution and cutting plane proofs and monotone computations
+Normal rank
@@ Property / cites work @@
+Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
+Normal rank
@@ Property / cites work @@
+A method for obtaining digital signatures and public-key cryptosystems
+Normal rank
@@ Property / cites work @@
+Q3140644
@@ Property / cites work: Q3140644 / rank @@
+Normal rank