| نویسندگان | Saeed Asaeedi - Farzad Didehvar |
|---|---|
| همایش | 2nd World Conference on Information Technology (WCIT-2011) |
| تاریخ برگزاری همایش | 2011-11-22 |
| محل برگزاری همایش | Antalya |
| شماره صفحات | 3 |
| نوع ارائه | سخنرانی |
| سطح همایش | بین المللی |
چکیده مقاله
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.
کلید واژه ها: Listing, P co-order, NP co-order, PO equivalent, NPO equivalent