Feasible Depth

Details Feasible Depth Feasible Depth

2007-01-19

arxiv.org/abs/cs/0701123v3

Computer Science

Computational Complexity

Accepted to Computation and Logic in the Real World, Proceedings of the 3rd Conference on Computability in Europe (CiE), 2007

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Feasible Depth does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Feasible Depth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Feasible Depth will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-651625