TY - GEN
T1 - Tailoring recursion to characterize non-deterministic complexity classes over arbitrary structures
AU - Bournez, O.
AU - Cucker, F.
AU - de Naurois, P. Jacobe
AU - Marion, J. Y.
PY - 2004/1/1
Y1 - 2004/1/1
N2 - We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L. Blum, M. Shub and S. Smale. We show that the levels of the polynomial hierarchy correspond to safe recursion with predicative minimization. The levels of the digital polynomial hierarchy correspond to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions.
AB - We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L. Blum, M. Shub and S. Smale. We show that the levels of the polynomial hierarchy correspond to safe recursion with predicative minimization. The levels of the digital polynomial hierarchy correspond to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions.
M3 - Conference contribution
AN - SCOPUS:84901006207
SN - 1402081405
SN - 9781402081408
T3 - IFIP Advances in Information and Communication Technology
SP - 409
EP - 422
BT - Exploring New Frontiers of Theoretical Informatics - IFIP 18th World Computer Congress TC1 and 3rd International Conference on Theoretical Computer Science, TCS 2004
PB - Springer New York LLC
T2 - IFIP 18th World Computer Congress, TC1 and 3rd International Conference on Theoretical Computer Science, TCS 2004
Y2 - 22 August 2004 through 27 August 2004
ER -