Enumeration order complexity equivalency

چکیده مقاله

The enumeration of elements of c.e sets in the theory of computability and computational complexity has already been investigated. However, the order of this enumeration and its time complexity has received less attention. Safilian and Didehvar in [1,2] investigated enumeration orders of elements of c.e sets by means of Turing machines. In this paper, we investigate the time complexity of these enumerations.To aim this, we define P and NP co-order sets and we presentPO and NPO equivalency classes. The main idea is effective enumeration, listing, and efficiency of function which is defined between two c.e. sets. It is possible that two listings and with equal enumeration orderbelong to different time complexity classes.