Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time
Copyright policy )Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time
We provide several machine-independent characterizations of deterministic complexity classes in the model of computation proposed by L. Blum, M. Shub and S. Smale. We provide a characterization of partial recursive functions over any arbitrary structure. We show that polynomial time over an arbitrary structure can be characterized in terms of safe recursion. We show that polynomial parallel time over an arbitrary structure can be characterized in terms of safe recursion with substitutions.
- French National Centre for Scientific Research France
- City University of Hong Kong China (People's Republic of)
- Lorraine Research Laboratory in Computer Science and its Applications France
- INSTITUT NATIONAL POLYTECHNIQUE DE LORRAINE France
- French Institute for Research in Computer Science and Automation France
function algebras, implicit complexity, Complexity of computation (including implicit computational complexity), complexity theory, Models of computation (Turing machines, etc.), Recursive functions and relations, subrecursive hierarchies, Shub, Smale model, Complexity classes (hierarchies, relations among complexity classes, etc.), [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Blum, Abstract and axiomatic computability and recursion theory, Blum-Shub-Smale model
function algebras, implicit complexity, Complexity of computation (including implicit computational complexity), complexity theory, Models of computation (Turing machines, etc.), Recursive functions and relations, subrecursive hierarchies, Shub, Smale model, Complexity classes (hierarchies, relations among complexity classes, etc.), [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Blum, Abstract and axiomatic computability and recursion theory, Blum-Shub-Smale model
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!