| ชื่อเรื่อง | : | Complexity of equivalence relations and preorders from computability theory |
| นักวิจัย | : | Ianovski, Egor , Miller, Russell , Ng, Keng Meng , Nies, Andre |
| คำค้น | : | DRNTU::Science::Mathematics::Mathematical logic |
| หน่วยงาน | : | Nanyang Technological University, Singapore |
| ผู้ร่วมงาน | : | - |
| ปีพิมพ์ | : | 2557 |
| อ้างอิง | : | Ianovski, E., Miller, R., Ng, K. M.,& Nies, A. (2014). Complexity of equivalence relations and preorders from computability theory. The journal of symbolic logic, 79(03), 859-881. , 1943-5886 , http://hdl.handle.net/10220/25392 , http://dx.doi.org/10.1017/jsl.2013.33 |
| ที่มา | : | - |
| ความเชี่ยวชาญ | : | - |
| ความสัมพันธ์ | : | The journal of symbolic logic |
| ขอบเขตของเนื้อหา | : | - |
| บทคัดย่อ/คำอธิบาย | : | We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relations R; S, a componentwise reducibility is de ned by R ≤ S ⇔ ∃f ∀x, y [xRy ↔ f(x) S f(y)]. Here f is taken from a suitable class of effective functions. For us the relations will be on natural numbers, and f must be computable. We show that there is a ∏ 0 1-complete equivalence relation, but no ∏ 0 k-complete for k≥2. We show that ∑ 0 k preorders arising naturally in the abovementioned areas are ∑ 0 k-complete. This includes polynomial time m-reducibility on exponential time sets, which is ∑ 0 2, almost inclusion on r.e. sets, which is ∑ 0 3, and Turing reducibility on r.e. sets, which is ∑ 0 4 . |
| บรรณานุกรม | : |
Ianovski, Egor , Miller, Russell , Ng, Keng Meng , Nies, Andre . (2557). Complexity of equivalence relations and preorders from computability theory.
กรุงเทพมหานคร : Nanyang Technological University, Singapore. Ianovski, Egor , Miller, Russell , Ng, Keng Meng , Nies, Andre . 2557. "Complexity of equivalence relations and preorders from computability theory".
กรุงเทพมหานคร : Nanyang Technological University, Singapore. Ianovski, Egor , Miller, Russell , Ng, Keng Meng , Nies, Andre . "Complexity of equivalence relations and preorders from computability theory."
กรุงเทพมหานคร : Nanyang Technological University, Singapore, 2557. Print. Ianovski, Egor , Miller, Russell , Ng, Keng Meng , Nies, Andre . Complexity of equivalence relations and preorders from computability theory. กรุงเทพมหานคร : Nanyang Technological University, Singapore; 2557.
|
ridm@nrct.go.th ระบบคลังข้อมูลงานวิจัยไทย รายการโปรดที่คุณเลือกไว้
