The complexity of total order structures

摘要

The relationship between the computational complexity of r.e. sets and of total orders on the sets is investigated. Total orders inherit some complexity properties from the fields over which they are defined, but also may be arbitrarily complex or have speedups independently of the field. This suggests that the total order structure itself possesses the complexity properties. Different complexity properties hold for total orders of different order types. In particular, whether the total order has a least or greatest element determines whether the complexity properties hold almost everywhere or infinitely often.