کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657867 | 690575 | 2005 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The computational complexity of distance functions of two-dimensional domains
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study the computational complexity of the distance function associated with a polynomial-time computable two-dimensional domains, in the context of the Turing machine-based complexity theory of real functions. It is proved that the distance function is not necessarily computable even if a two-dimensional domain is polynomial-time recognizable. On the other hand, if both the domain and its complement are strongly polynomial-time recognizable, then the distance function is polynomial-time computable if and only if P=NP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 337, Issues 1â3, 9 June 2005, Pages 360-369
Journal: Theoretical Computer Science - Volume 337, Issues 1â3, 9 June 2005, Pages 360-369
نویسندگان
Arthur W. Chou, Ker-I Ko,