کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657754 | 690565 | 2005 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Resource bounded symmetry of information revisited
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study symmetry of information for some variants of distinguishing complexity CD where CD(x) is the length of a shortest program which accepts x and only x. We show relativized worlds where symmetry of information does not hold in a strong way for deterministic and nondeterministic polynomial time distinguishing complexities CDpoly and CNDpoly. On the other hand, for nondeterministic polynomial time distinguishing complexity with randomness, CAMDpoly, we show that symmetry of information holds for most pairs of strings in any set in NP. Our techniques extend work of Buhrman et al. (Language compression and pseudorandom generators, in: Proc. 19th IEEE Conf. on Computational Complexity, IEEE, New York, 2004, pp. 15-28) on language compression by AM algorithms, and have the following application to the compression of samplable sources, introduced in Trevisan et al. (Compression of sample sources, in: Proc. 19th IEEE Conf. on Computational Complexity, IEEE, New York, 2004, pp. 1-15): any element x in the support of a polynomial time samplable source X can be given a description of size -logPr[X=x]+O(log3n), from which x can be recovered by an AM algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 345, Issues 2â3, 22 November 2005, Pages 386-405
Journal: Theoretical Computer Science - Volume 345, Issues 2â3, 22 November 2005, Pages 386-405
نویسندگان
Troy Lee, Andrei Romashchenko,