On genuinely time bounded computations
Lecture notes in computer sciencePublished 1 December 2005
Friedhelm Meyer auf der Heide
Citations13
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
In this paper genuine complexity classes for given operation sets S are defined, following ideas due to Karpinski and the author from [KaM 88], and results on genuine computability, lower bound methods, as well as examples for complexity gaps and separated complexity classes are surveyed.
Abstract
This survey paper presents a complexity theoretical approach to genuinely time bounded computations. Such computations are executed by random access machines with given set $$S \subseteq \{ + , - ,*,DIV,...\}$$ of arithmetic operations. The uniform cost measure is assumed, and the input is given integer by integer, not bit by bit. "Genuinely" (also called "strongly" in the literature) means that we measure the time complexity T(n) as the worst case runtime over all inputs consisting of n integers (not of n bits). Computability and complexity now heavily depend on the operation set S. In this paper genuine complexity classes for given operation sets S are defined, following ideas due to Karpinski and the author from [KaM 88]. Furthermore, results on genuine computability, lower bound methods, as well as examples for complexity gaps and separated complexity classes are surveyed.
Keywords
Computer ScienceMathematics
American Mathematical MonthlyCombinatorial Optimization: Algorithms and Complexity.
6,028 Citations1984David Johnson, Christos H. Papadimitriou +1 more
A new polynomial-time algorithm for linear programming
1,014 Citations1984Narendra Karmarkar
It is proved that given a polytopeP and a strictly interior point a εP, there is a projective transformation of the space that mapsP, a toP′, a′ having the following property: the ratio of the radius of the smallest sphere with center a′, containingP′ to theradius of the largest sphere withCenter a′ contained inP′ isO(n).
Lower bounds for algebraic computation trees
525 Citations1983Michael Ben-Or
All the apparently known lower bounds for linear decision trees are extended to bounded degree algebraic decision trees, thus answering the open questions raised by Steele and Yao [20].
Operations ResearchA Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
485 Citations1986Éva Tardos
This work gives a polynomial algorithm for the minimum cost flow and multicommodity flow problems in which the number of arithmetic steps is independent of the size of the costs and capacities.
Proceedings of the American Mathematical SocietyOn the Betti numbers of real varieties
485 Citations1964John Milnor
Journal of AlgorithmsLower bounds for algebraic decision trees
152 Citations1982John Steele, Andrew Chi-Chih Yao
A topological method is given for obtaining lower bounds for the height of algebraic decision trees and an Ω(n2) bound is obtained for trees with bounded-degree polynomial tests, thus extending the Dobkin-Lipton result for linear trees.
Lecture notes in computer scienceOn the power of random access machines
137 Citations1979Arnold Schönhage
The main results are NP ...
SIAM Journal on ComputingTowards a Genuinely Polynomial Algorithm for Linear Programming
116 Citations1983Nimrod Megiddo
This paper presents a genuinely polynomial algorithm for the simpler problem of solving linear inequalities with at most two variables per inequality.
Journal of the ACMA Polynomial Linear Search Algorithm for the <i>n</i> -Dimensional Knapsack Problem
83 Citations1984Friedhelm Meyer auf der Heide
Journal of the ACMOn the Optimality of Some Set Algorithms
61 Citations1972Edward M. Reingold
The es tab l i shment of lower bounds on the number of comparisons necessary to solve various combinator problems is considered and the maximum of a set of n real numbers cannot be computed in fewer than n 1 comparisons if comparisons of only l inear funct ions of the numbers are permitted.
Acta InformaticaBerechnung und Programm. II
59 Citations1973Volker Strassen
An algebraic equivalent of the notion of computation is defined and it is shown that for a large class of computational problems no speed-up may be obtained by the use of branching, except for a small set of inputs.
On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines
58 Citations1988Lenore Blum, M. Shub +1 more
A model for computation over an arbitrary (ordered) ring R is presented, which reflects the special mathematical character of the underlying ring R and provides a natural setting for studying foundational issues concerning algorithms in numerical analysis.
Elementary bounds for presburger arithmetic
37 Citations1973Derek C. Oppen
It is proved here that there exists a decision procedure for this theory of integers under addition, involving quantifier elimination, for which there is a superexponential upper bound on the size of formula produced when all variables have been eliminated.
Lecture notes in computer scienceA lower bound of 1/2n2 on linear search programs for the knapsack problem
32 Citations1976David Dobkin, Richard J. Lipton
The result presented here is the first lower bound of better than n log n given for an NP-complete problem for a model that is actually used in practice and derived by combining results on linear search tree complexity with results from threshold logic.
Journal of the ACMLower bounds for solving linear diophantine equations on random access machines
27 Citations1985Friedhelm Meyer auf der Heide
Lower bounds that depend on the input size, as is necessary for L, the knapsack problem, are proved and an &OHgr;(1) lower bound is obtained for RAMS recognizing L recognizing L or L recognizing RAMS.
Theoretical Computer ScienceSimulating probabilistic by deterministic algebraic computation trees
22 Citations1985Friedhelm Meyer auf der Heide
The result for ACTs establishes a weaker version of results previously shown by the author for LSAs, namely that LSAs can only be slightly sped up by their nondeterministic versions.
Journal of the ACMFast algorithms for <i>N</i> -dimensional restrictions of hard problems
21 Citations1988Friedhelm Meyer auf der Heide
This result generalizes the construction of a polynomial LSA for the knapsack problem and destroys the hope of proving nonpolynomial lower bounds on LSAs for any problem that can be recognized by a PRAM as above with 2 poly(n) processors in poly(italic) time.
Information and ComputationOn the limits of computations with the floor function
20 Citations1988László Babai, Bettina Just +1 more
It is shown by topological arguments that by ACTs one cannot decide certain classes of languages, examples of which are Q n and the set of tuples (x1,…,xn) ∈ R n that have components which are Z -linearly or algebraically dependent.
Division is good
13 Citations1979Janoš Šimon
It is shown that in certain situations parallelism and stochastic features ('distributed random choices') are provably more powerful than either parallelism or randomness alone.
Lecture notes in computer scienceOn computations with integer division
6 Citations1988Bettina Just, Fb Mathematik +3 more
Lecture notes in computer scienceOn the complexity of genuinely polynomial computation
4 Citations2005Marek Karpiński, Friedhelm Meyer auf der Heide