گام برداری تصادفی غیر متقارن بعنوان نشانه ایی از پیچیدگی در مسایل گستاخ

شناخت ماهیت فضاهای حالت در مسایل گستاخ و خصوصیات هندسی آنها نقش عمده ایی در ردیابی پیچیدگی آنها دارد. استراتژی معمول در این زمینه بر مطالعه مسایلی متمرکز شده است که از نظر تیوری پیچیدگی NP-Complete می باشند. مشهورترین مساله از این خانواده مساله ارضا پذیری فرمولهایی است که بصورت K-CNF نگاشته می شوند و با نام K-SAT شناخته می شود. مساله K-SAT برای مقادیر K≤2 دارای راه حل با پیچیدگی زمانی چند جمله ایست، حال آنکه این پیچیدگی برای K≥3 بصورت نمایی در خواهد آمد. در این مقاله با بررسی الگوریتم تصادفی حل این مساله به تحلیل سرمنشاء بروز این پیچیدگی خواهیم پرداخت. ظهور این پیچیدگی را در قالب نیاز به زمان نمایی گام بردار تصادفی غیرمتقارن برای رسیدن به مبدا تفسیر خواهیم کرد.

Keywords:

مسایل گستاخ , الگوریتم تصادفی , گام برداری غیر متقارن , همگرایی در زمان نمایی , تحویل پذیری