Feasible Depth

DOI10.1007/978-3-540-73001-9_24MaRDI QIDQ5425324zbMATH OpenOpenAlexFDO

Authors David Doty, Philippe Moser

Publication date 13 November 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0701123

zbMATH Keywords

depthdimensionfinite-statepolynomial-timerandomness

Mathematics Subject Classification ID

Applications of computability and recursion theory (03D80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: 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.

Recommendations

• Relativized depth
• scientific article; zbMATH DE number 3966267
• Local depth
• Regression Depth
• Computational depth: Concept and applications
• Constant Depth Reducibility
• Depth functions as measures of representativeness
• Flexible integrated functional depths
• Strong depth relevance
• Enclosing depth and other depth measures

Cited in

(15)

• Lowness and logical depth
• Limit-depth and DNR degrees
• Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report)
• Polylog depth, highness and lowness for E
• Finite state incompressible infinite sequences
• An almost deep degree
• Concerns with functional depth
• Depth, highness and DNR degrees
• On the Polynomial Depth of Various Sets of Random Strings
• On the difference between finite-state and pushdown depth
• Low-depth witnesses are easy to find
• Pushdown and Lempel-Ziv depth
• Pebble-depth
• Finite state complexity
• A normal sequence compressed by PPM* but not by Lempel-Ziv 78

This page was built for publication: Feasible Depth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5425324)