scientific article; zbMATH DE number 1136087
From MaRDI portal
Publication:4381398
zbMath0893.03020MaRDI QIDQ4381398
Publication date: 20 July 1998
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
deterministicpolynomial timecomplexity classesnondeterministicexponential timep-optimal proof systemsmany-one complete languagesmany-one complete setsp-simulation
Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items
A Parameterized Halting Problem ⋮ NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Optimal proof systems imply complete sets for promise classes ⋮ Reduction of Hilbert-type proof systems to the if-then-else equational logic ⋮ On an optimal propositional proof system and the structure of easy subsets of TAUT. ⋮ Hardness and optimality in QBF proof systems modulo NP
This page was built for publication:
