کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950822 | 1441041 | 2017 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Did the train reach its destination: The complexity of finding a witness
ترجمه فارسی عنوان
آیا قطار به مقصد رسید: پیچیدگی یافتن یک شاهد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Recently, Dohrau et al. studied a zero-player game on switch graphs and proved that deciding the termination of the game is in NPâ©coNP. In this short paper, we show that the search version of this game on switch graphs, i.e., the task of finding a witness of termination (or of non-termination) is in PLS.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 121, May 2017, Pages 17-21
Journal: Information Processing Letters - Volume 121, May 2017, Pages 17-21
نویسندگان
Karthik C. S. Karthik C. S.,