scientific article; zbMATH DE number 1304339
From MaRDI portal
Publication:4251070
zbMath0924.03072MaRDI QIDQ4251070
Publication date: 16 November 1999
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
deterministic algorithmmany-one reducibilitytime-complexitynondeterministic algorithmsoptimal acceptor for a languagep-cylinderp-optimal proof system
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20)
Related Items (7)
Nondeterministic functions and the existence of optimal proof systems ⋮ Optimal heuristic algorithms for the image of an injective function ⋮ On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography ⋮ Total nondeterministic Turing machines and a p-optimal proof system for SAT ⋮ Hard Instances of Algorithms and Proof Systems ⋮ Consistency and Optimality ⋮ On an optimal propositional proof system and the structure of easy subsets of TAUT.
This page was built for publication:
