Publication:4251070
From MaRDI portal
zbMath0924.03072MaRDI QIDQ4251070
Publication date: 16 November 1999
deterministic algorithm; many-one reducibility; time-complexity; nondeterministic algorithms; optimal acceptor for a language; p-cylinder; p-optimal proof system
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
03F20: Complexity of proofs
Related Items
Hard Instances of Algorithms and Proof Systems, On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography, Nondeterministic functions and the existence of optimal proof systems, On an optimal propositional proof system and the structure of easy subsets of TAUT., Optimal heuristic algorithms for the image of an injective function, Total nondeterministic Turing machines and a p-optimal proof system for SAT, Consistency and Optimality