A Note on The Functions Which Are Not Polynomial Time Computable From Their Graphs

DOI10.4288/jafpos1956.9.17zbMath0858.03042MaRDI QIDQ4885644

Juichi Shinoda, Asae Mochizuki

Publication date: 28 July 1996

Published in: Annals of the Japan Association for Philosophy of Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4288/jafpos1956.9.17

zbMATH Keywords

polynomial-time reducibility; functions on natural numbers

Mathematics Subject Classification ID

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

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

03D20: Recursive functions and relations, subrecursive hierarchies