Speedup for natural problems and noncomputability
From MaRDI portal
Publication:620964
DOI10.1016/J.TCS.2010.09.029zbMATH Open1206.68177OpenAlexW2057550516MaRDI QIDQ620964FDOQ620964
Authors: 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
Recommendations
- Non-elementary speed-ups in logic calculi
- Speed-Up Theorems in Type-2 Computation
- Complexity of nonuniform computations for certain discrete problems
- Improving the efficiency of non-deterministic computations
- scientific article; zbMATH DE number 1223552
- Natural computation and non-Turing models of computation
- Faster exact solutions for some NP-hard problems.
- Nonconstructive advances in polynomial-time complexity
- On superlinear speedups
- scientific article; zbMATH DE number 45545
optimal algorithmcoNP-complete languagepropositional proof systemspeedabilitysuperpolynomial speedup
Cites Work
- How to multiply matrices faster
- The relative efficiency of propositional proof systems
- A Machine-Independent Theory of the Complexity of Recursive Functions
- On the Asymptotic Complexity of Matrix Multiplication
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Title not available (Why is that?)
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Title not available (Why is that?)
- Title not available (Why is that?)
- On slicewise monotone parameterized problems and optimal proof systems for TAUT
- A characterization of complexity sequences
- Computational speed-up by effective operators
Cited In (4)
This page was built for publication: Speedup for natural problems and noncomputability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q620964)
