Nondeterministic functions and the existence of optimal proof systems (Q837177): Difference between revisions

@@ Property / DOI @@
-.1016/j.tcs.2009.05.021
@@ Property / DOI: 10.1016/j.tcs.2009.05.021 / rank @@
-Normal rank
@@ Property / Wikidata QID @@
+Q57950025
@@ Property / Wikidata QID: Q57950025 / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W1996110613
@@ Property / OpenAlex ID: W1996110613 / rank @@
+Normal rank
@@ Property / cites work @@
+The monotone circuit complexity of Boolean functions
+Normal rank
@@ Property / cites work @@
+Q4321931
@@ Property / cites work: Q4321931 / rank @@
+Normal rank
@@ Property / cites work @@
+The Deduction Theorem for Strong Propositional Proof Systems
+Normal rank
@@ Property / cites work @@
+Classes of representable disjoint \textsf{NP}-pairs
+Normal rank
@@ Property / cites work @@
+Tuples of disjoint \(\mathsf{NP}\)-sets
@@ Property / cites work: Tuples of disjoint \(\mathsf{NP}\)-sets / rank @@
+Normal rank
@@ Property / cites work @@
+On the correspondence between arithmetic theories and propositional proof systems – a survey
+Normal rank
@@ Property / cites work @@
+Non-automatizability of bounded-depth Frege proofs
+Normal rank
@@ Property / cites work @@
+Lower bounds for cutting planes proofs with small coefficients
+Normal rank
@@ Property / cites work @@
+On Interpolation and Automatization for Frege Systems
+Normal rank
@@ Property / cites work @@
+Quantitative Relativizations of Complexity Classes
+Normal rank
@@ Property / cites work @@
+Does the polynomial hierarchy collapse if onto functions are invertible?
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory
+Normal rank
@@ Property / cites work @@
+Structure in Approximation Classes
@@ Property / cites work: Structure in Approximation Classes / rank @@
+Normal rank
@@ Property / cites work @@
+Inverting onto functions.
@@ Property / cites work: Inverting onto functions. / rank @@
+Normal rank
@@ Property / cites work @@
+Oracles That Compute Values
@@ Property / cites work: Oracles That Compute Values / rank @@
+Normal rank
@@ Property / cites work @@
+Separability and one-way functions
@@ Property / cites work: Separability and one-way functions / rank @@
+Normal rank
@@ Property / cites work @@
+Reductions between disjoint NP-pairs
@@ Property / cites work: Reductions between disjoint NP-pairs / rank @@
+Normal rank
@@ Property / cites work @@
+Disjoint NP-Pairs
@@ Property / cites work: Disjoint NP-Pairs / rank @@
+Normal rank
@@ Property / cites work @@
+Canonical disjoint NP-pairs of propositional proof systems
+Normal rank
@@ Property / cites work @@
+The Informational Content of Canonical Disjoint NP-Pairs
+Normal rank
@@ Property / cites work @@
+Complexity Measures for Public-Key Cryptosystems
@@ Property / cites work: Complexity Measures for Public-Key Cryptosystems / rank @@
+Normal rank
@@ Property / cites work @@
+Q4452100
@@ Property / cites work: Q4452100 / rank @@
+Normal rank
@@ Property / cites work @@
+NONDETERMINISTICALLY SELECTIVE SETS
@@ Property / cites work: NONDETERMINISTICALLY SELECTIVE SETS / rank @@
+Normal rank
@@ Property / cites work @@
+On some natural complete operators
@@ Property / cites work: On some natural complete operators / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal proof systems imply complete sets for promise classes
+Normal rank
@@ Property / cites work @@
+UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
+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 @@
+Propositional proof systems, the consistency of first order theories and the complexity of computations
+Normal rank
@@ Property / cites work @@
+Some consequences of cryptographical conjectures for \(S_2^1\) and EF
+Normal rank
@@ Property / cites work @@
+The complexity of optimization problems
@@ Property / cites work: The complexity of optimization problems / rank @@
+Normal rank
@@ Property / cites work @@
+On gamma-reducibility versus polynomial time many-one reducibility
+Normal rank
@@ Property / cites work @@
+Q4251070
@@ Property / cites work: Q4251070 / rank @@
+Normal rank
@@ Property / cites work @@
+Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
+Normal rank
@@ Property / cites work @@
+A hierarchy based on output multiplicity
@@ Property / cites work: A hierarchy based on output multiplicity / rank @@
+Normal rank
@@ Property / cites work @@
+Q3221403
@@ Property / cites work: Q3221403 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for resolution and cutting plane proofs and monotone computations
+Normal rank
@@ Property / cites work @@
+Q4215637
@@ Property / cites work: Q4215637 / rank @@
+Normal rank
@@ Property / cites work @@
+On reducibility and symmetry of disjoint NP pairs.
+Normal rank
@@ Property / cites work @@
+Q4375799
@@ Property / cites work: Q4375799 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3758729
@@ Property / cites work: Q3758729 / rank @@
+Normal rank
@@ Property / cites work @@
+On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP
+Normal rank
@@ Property / cites work @@
+Q4263798
@@ Property / cites work: Q4263798 / 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 @@
+Q5422270
@@ Property / cites work: Q5422270 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity and structure
@@ Property / cites work: Complexity and structure / rank @@
+Normal rank
@@ Property / cites work @@
+A taxonomy of complexity classes of functions
@@ Property / cites work: A taxonomy of complexity classes of functions / rank @@
+Normal rank
@@ Property / cites work @@
+Relative complexity of checking and evaluating
@@ Property / cites work: Relative complexity of checking and evaluating / rank @@
+Normal rank
@@ Property / cites work @@
+#P-COMPLETENESS VIA MANY-ONE REDUCTIONS
@@ Property / cites work: #P-COMPLETENESS VIA MANY-ONE REDUCTIONS / rank @@
+Normal rank
@@ Property / DOI @@
+.1016/J.TCS.2009.05.021
@@ Property / DOI: 10.1016/J.TCS.2009.05.021 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:837177