On proving time constructibility of functions

DOI10.1016/0304-3975(85)90015-5zbMath0566.68042OpenAlexW2000496852MaRDI QIDQ1059393

Kojiro Kobayashi

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90015-5

zbMATH Keywords

time complexityTuring machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Related Items (2)

Alternating time versus deterministic time: A separation ⋮ Deterministic Turing machines in the range between real-time and linear-time.

Cites Work

• Circuit-size lower bounds and non-reducibility to sparse sets
• Unnamed Item

This page was built for publication: On proving time constructibility of functions