caa a22 4500 469034017 CHVBK 20180323132751.0 cr unu---uuuuu 170328e19920601xx s 000 0 eng 10.1007/BF01201998 doi (NATIONALLICENCE)springer-10.1007/BF01201998 A new recursion-theoretic characterization of the polytime functions [Elektronische Daten] [Spephen Bellantoni, Stephen Cook] We give a recursion-theoretic characterization of FP which describes polynomial time computation independently of any externally imposed resource bounds. In particular, this syntactic characterization avoids the explicit size bounds on recursion (and the initial function 2|x|·|y|) of Cobham. Birkhäuser Verlag, 1992 Recursion theory nationallicence Cobham nationallicence Polynomial Time nationallicence 68Q15 nationallicence 03D20 nationallicence 68Q05 nationallicence Bellantoni Spephen Department of Computer Science, University of Toronto, M5S 1A4, Toronto, Ontario, Canada aut Cook Stephen Department of Computer Science, University of Toronto, M5S 1A4, Toronto, Ontario, Canada aut computational complexity Birkhäuser-Verlag 2/2(1992-06-01), 97-110 1016-3328 2:2<97 1992 2 37 https://doi.org/10.1007/BF01201998 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01201998 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bellantoni Spephen Department of Computer Science, University of Toronto, M5S 1A4, Toronto, Ontario, Canada aut NATIONALLICENCE 700 1- Cook Stephen Department of Computer Science, University of Toronto, M5S 1A4, Toronto, Ontario, Canada aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag 2/2(1992-06-01), 97-110 1016-3328 2:2<97 1992 2 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer