Some consequences of cryptographical conjectures for \(S_2^1\) and EF
From MaRDI portal
Publication:1383164
DOI10.1006/inco.1997.2674zbMath0892.68029OpenAlexW2068363706WikidataQ106785148 ScholiaQ106785148MaRDI QIDQ1383164
Publication date: 4 May 1998
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.1997.2674
Related Items (33)
On the automatizability of resolution and related propositional proof systems ⋮ Interpolation systems for ground proofs in automated deduction: a survey ⋮ On the complexity of resolution with bounded conjunctions ⋮ Nondeterministic functions and the existence of optimal proof systems ⋮ Feasible Interpolation for QBF Resolution Calculi ⋮ Dual weak pigeonhole principle, Boolean complexity, and derandomization ⋮ Circuit principles and weak pigeonhole variants ⋮ Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds ⋮ INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Classes of representable disjoint \textsf{NP}-pairs ⋮ The polynomial and linear hierarchies in models where the weak pigeonhole principle fails ⋮ Extended clause learning ⋮ On reducibility and symmetry of disjoint NP pairs. ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ Tuples of disjoint \(\mathsf{NP}\)-sets ⋮ Tautologies from Pseudo-Random Generators ⋮ Towards a unified complexity theory of total functions ⋮ Abelian groups and quadratic residues in weak arithmetic ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Mean-payoff games and propositional proofs ⋮ Understanding cutting planes for QBFs ⋮ The Complexity of Propositional Proofs ⋮ Quantum deduction rules ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Proof Complexity of Non-classical Logics ⋮ Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes ⋮ ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION ⋮ Short Proofs Are Hard to Find ⋮ Non-standard finite fields over \(I\Delta_0+\Omega_1\) ⋮ Do there exist complete sets for promise classes? ⋮ A model-theoretic characterization of the weak pigeonhole principle ⋮ How QBF expansion makes strategy extraction hard
Cites Work
- Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
- Bounded arithmetic and the polynomial hierarchy
- Fragments of Bounded Arithmetic and Bounded Query Classes
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Quantified propositional calculi and fragments of bounded arithmetic
- RSA and Rabin Functions: Certain Parts are as Hard as the Whole
- Every Prime Has a Succinct Certificate
- A method for obtaining digital signatures and public-key cryptosystems
- The relative efficiency of propositional proof systems
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Interpolation by a Game
- Lower bounds to the size of constant-depth propositional proofs
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for cutting planes proofs with small coefficients
- Lower bounds for resolution and cutting plane proofs and monotone computations
- A lower bound for the complexity of Craig's interpolants in sentential logic
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Some consequences of cryptographical conjectures for \(S_2^1\) and EF
