Abstract
The computational complexity of a Delta 2 set will be calibrated by the amount of changes needed for any of its computable approximations. Firstly, we study Martin-Loef random sets, where we quantify the changes of initial segments. Secondly, we look at c.e. sets, where we quantify the overall amount of changes by obedience to cost functions. Finally, we combine the two settings. The discussions lead to three basic principles on how complexity and changes relate.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.