On genuinely time bounded computations

DOI10.1007/BFB0028969MaRDI QIDQ5096139zbMATH OpenFDO

Authors Friedhelm Meyer auf der Heide

Publication date 16 August 2022

Published in STACS 89 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0028969

zbMATH Keywords

arithmetic operationarithmetic progressionknapsack problemPresburger arithmeticrandom access machine

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 18636
• A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
• scientific article; zbMATH DE number 827987
• Strong time bounds: Non-computable bounds and a hierarchy theorem
• TIME BOUNDED COMPUTATIONS OVER THE REALS

Cites work

• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Berechnung und Programm. II
• scientific article; zbMATH DE number 4131650 (Why is no real title available?)
• scientific article; zbMATH DE number 3913670 (Why is no real title available?)
• scientific article; zbMATH DE number 4072374 (Why is no real title available?)
• scientific article; zbMATH DE number 18636 (Why is no real title available?)
• scientific article; zbMATH DE number 3478862 (Why is no real title available?)
• scientific article; zbMATH DE number 3628385 (Why is no real title available?)
• scientific article; zbMATH DE number 3637614 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• Komplexität von Entscheidungsproblemen. Ein Seminar
• Lower bounds for algebraic decision trees
• Lower bounds for solving linear diophantine equations on random access machines
• On the Betti Numbers of Real Varieties
• On the limits of computations with the floor function
• On the Optimality of Some Set Algorithms
• Simulating probabilistic by deterministic algebraic computation trees
• Towards a Genuinely Polynomial Algorithm for Linear Programming

Cited in

(14)

• Sharply bounded alternation and quasilinear time
• Timed Sets, Functional Complexity, and Computability
• scientific article; zbMATH DE number 3860251 (Why is no real title available?)
• Computing in Finite Time
• scientific article; zbMATH DE number 4160128 (Why is no real title available?)
• scientific article; zbMATH DE number 5622695 (Why is no real title available?)
• scientific article; zbMATH DE number 17551 (Why is no real title available?)
• scientific article; zbMATH DE number 18636 (Why is no real title available?)
• Lower bounds on algebraic random access machines
• On lower bounds for the time of computation
• scientific article; zbMATH DE number 827987 (Why is no real title available?)
• Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
• Time-Complexity Semantics for Feasible Affine Recursions
• Strong time bounds: Non-computable bounds and a hierarchy theorem

This page was built for publication: On genuinely time bounded computations

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