Speedup for natural problems and noncomputability

DOI10.1016/j.tcs.2010.09.029zbMath1206.68177OpenAlexW2057550516MaRDI QIDQ620964

Hunter Monroe

Publication date: 2 February 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.09.029

zbMATH Keywords

optimal algorithmcoNP-complete languagepropositional proof systemspeedabilitysuperpolynomial speedup

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (4)

A Parameterized Halting Problem ⋮ Optimal heuristic algorithms for the image of an injective function ⋮ On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography ⋮ Hard Instances of Algorithms and Proof Systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to multiply matrices faster
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• On Slicewise Monotone Parameterized Problems and Optimal Proof Systems for TAUT
• On the Asymptotic Complexity of Matrix Multiplication
• A characterization of complexity sequences
• The relative efficiency of propositional proof systems
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Computational speed-up by effective operators

This page was built for publication: Speedup for natural problems and noncomputability