Publication:4381398
From MaRDI portal
zbMath0893.03020MaRDI QIDQ4381398
Publication date: 20 July 1998
deterministic; polynomial time; complexity classes; nondeterministic; exponential time; p-optimal proof systems; many-one complete languages; many-one complete sets; p-simulation
03D15: Complexity of computation (including implicit computational complexity)
03B05: Classical propositional logic
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03F20: Complexity of proofs
Related Items
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, A Parameterized Halting Problem