On optimal algorithms and optimal proof systems

DOI10.1007/3-540-49116-3_51MaRDI QIDQ4251070zbMATH OpenFDO

Authors Jochen Messner

Publication date 16 November 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-49116-3_51

zbMATH Keywords

deterministic algorithmmany-one reducibilitynondeterministic algorithmsoptimal acceptor for a languagep-cylinderp-optimal proof systemtime-complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Optimal acceptors and optimal proof systems
• scientific article; zbMATH DE number 1500532
• Semialgebraic Proofs and Efficient Algorithm Design
• scientific article; zbMATH DE number 5201477
• Hard instances of algorithms and proof systems
• Hard instances of algorithms and proof systems
• Lectures on proof verification and approximation algorithms
• scientific article; zbMATH DE number 2119703
• scientific article; zbMATH DE number 4024619
• Optimal Proofs of Determinacy

Cited in

(24)

• Optimal deterministic algorithm generation
• Efficient rational proofs for space bounded computations
• 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
• Optimality proof of the Kise-Ibaraki-Mine algorithm
• Optimal Proximity Proofs Revisited
• On optimal inverters
• Consistency and optimality
• scientific article; zbMATH DE number 5999718 (Why is no real title available?)
• Optimal acceptors and optimal proof systems
• On p-optimal proof systems and logics for PTIME
• On an optimal randomized acceptor for graph nonisomorphism
• On an optimal deterministic algorithm for SAT
• scientific article; zbMATH DE number 512976 (Why is no real title available?)
• Optimal proof systems for propositional logic and complete sets
• scientific article; zbMATH DE number 2019634 (Why is no real title available?)
• OPTIMAL PROOFS OF DETERMINACY II
• Consistency, optimality, and incompleteness
• Semialgebraic Proofs and Efficient Algorithm Design
• scientific article; zbMATH DE number 5201477 (Why is no real title available?)
• 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

This page was built for publication: On optimal algorithms and optimal proof systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4251070)