On genuinely time bounded computations

DOI10.1007/BFb0028969zbMath1492.68056MaRDI QIDQ5096139

Friedhelm Meyer auf der Heide

Publication date: 16 August 2022

Published in: STACS 89 (Search for Journal in Brave)

zbMATH Keywords

arithmetic progression; knapsack problem; Presburger arithmetic; random access machine; arithmetic operation

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Lower bounds on algebraic random access machines, Strong time bounds: Non-computable bounds and a hierarchy theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the limits of computations with the floor function
• Komplexität von Entscheidungsproblemen. Ein Seminar
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• Simulating probabilistic by deterministic algebraic computation trees
• Berechnung und Programm. II
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Towards a Genuinely Polynomial Algorithm for Linear Programming
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• Lower bounds for solving linear diophantine equations on random access machines
• Lower bounds for algebraic decision trees
• On the Optimality of Some Set Algorithms
• On the Betti Numbers of Real Varieties