Feasible Depth
| dc.creator | Doty, David | |
| dc.creator | Moser, Philippe | |
| dc.date | 2007-01-19 | |
| dc.date | 2007-04-11 | |
| dc.date.accessioned | 2026-07-07T08:16:59Z | |
| dc.date.available | 2026-07-07T08:16:59Z | |
| dc.description | This paper introduces two complexity-theoretic formulations of Bennett's logical depth: finite-state depth and polynomial-time depth. It is shown that for both formulations, trivial and random infinite sequences are shallow, and a slow growth law holds, implying that deep sequences cannot be created easily from shallow sequences. Furthermore, the E analogue of the halting language is shown to be polynomial-time deep, by proving a more general result: every language to which a nonnegligible subset of E can be reduced in uniform exponential time is polynomial-time deep. | |
| dc.description | Accepted to Computation and Logic in the Real World, Proceedings of the 3rd Conference on Computability in Europe (CiE), 2007 | |
| dc.identifier | https://arxiv.org/abs/cs/0701123 | |
| dc.identifier | http://arxiv.org/abs/cs/0701123 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/133978 | |
| dc.subject | Computational Complexity | |
| dc.subject | Information Theory | |
| dc.title | Feasible Depth | |
| dc.type | text |