Current Proceedings on Technology

Current Proceedings on Technology

Enumeration order complexity equivalency

Yazarlar: Saeed Asaeedi, Farzad Didehvar

Cilt 1 , Sayı - , 2012 , Sayfalar -

Konular:-

Anahtar Kelimeler:Listing,P co-order,NP co-order,PO equivalent,NPO equivalent    

Özet: 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 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 h and g with equal enumeration orderbelong to different time complexity classes.

ATIFLAR
Atıf Yapan Eserler
Henüz Atıf Yapılmamıştır
KAYNAK GÖSTER
BibTex
KOPYALA
@article{2012, title={Enumeration order complexity equivalency}, volume={1}, number={0}, publisher={Current Proceedings on Technology }, author={Saeed Asaeedi, Farzad Didehvar}, year={2012} }
APA
KOPYALA
Saeed Asaeedi, Farzad Didehvar. (2012). Enumeration order complexity equivalency (Vol. 1). Vol. 1. Current Proceedings on Technology .
MLA
KOPYALA
Saeed Asaeedi, Farzad Didehvar. Enumeration Order Complexity Equivalency. no. 0, Current Proceedings on Technology , 2012.
Atıf Görüntüle
PDF Görüntüle
Kaynak Görüntüle
Paylaş
Dergi Bilgileri