کلاس پی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در نظریه پیچیدگی محاسباتی، کلاس P یکی از پایه ترین کلاس‌های پیچیدگی است. این کلاس، شامل همهٔ مسئله‌های تصمیمی است که می‌توانند با استفاده از پیچیدگی زمانی چندجمله‌ای، با کمک ماشین تورینگ پایستار حل شوند.
کبهام در قضیه‌اش ذکر می‌کند که کلاس P در واقع مشخص کنندهٔ این است که یک مسئله قابل حل‌شدن و پیگیری هست یا نه؛ با این وجود در عمل مسائلی هستند که در این دسته قرار ندارند و راه‌حل‌های عملی دارند، و مسائلی هستند که در این دسته قرار دارند اما راه حل عملی ندارند.

تعریف[ویرایش]

زبان L در کلاس P قرار دارد اگر و تنها اگر ماشین تورینگ M وجود داشته باشد به قسمی که:

  • M در زمان چندجمله‌ای بر روی همهٔ ورودی‌ها اجرا شود.
  • به ازای هر x در L، خروجی M مساوی ۱ باشد.
  • به ازای هر x که در L نباشد، خروجی M صفر باشد

همچنین می‌توان P را به صورت دسته‌ای از مدارهای دودویی دید. زبان L در کلاس P قرار می گیرداگر و تنها اگر یک دسته از مدارهای دودویی وجود داشته باشد \{C_n:n \in \mathbb{N}\} به قسمی که:

  • برای هر n \in \mathbb{N} داشته باشیم، C_n بتواندn بیت را به عنوان ورودی و ۱ بیت را به عنوان خروجی بدهد.
  • برای هر x که در L باشد، C_{|x|}(x)=1
  • برای هر x که در L نباشد، C_{|x|}(x)=0

مسائل مهم دستهٔ P[ویرایش]

مسائل طبیعی زیادی در کلاس P قرار می‌گیرند که از میان آن‌ها به مسائلی مانند مسائل برنامه ریزی خطی، محاسبهٔ بزرگترین مقسوم علیه مشترک و پیدا کردن بیشترین تطابق در گراف‌ها اشاره کرد. در سال ۲۰۰۲ اثبات شد که مسئلهٔ اثبات اینکه یک عدد عدد اول است در کلاس P قرار می‌گیرد.

ارتباط با کلاس‌های دیگر[ویرایش]

کلاس عمومی تر کلاس پی، NP نام دارد که کلاسی از مسئله‌های تصمیم است ک به کمک ماشین تورینگ ناپایستار که در زمان چندجمله‌ای اجرا می‌شود، تصمیم گیری می‌شوند. P در واقع یک زیر مجموعه از NP و co-NP است، حال آنکه مسئله برابری پی و ان پی بدون اثبات باقی مانده است.

P همچنین معادل L، کلاس مسائل قابل حل در مرتبهٔ حافظهٔ لگاریتمی، در نظر گرفته می‌شود. تصمیم گیرنده‌ای که از O(\log n) حافظه استفاده می‌کند، نمی‌تواند بیش از 2^{O(\log n)} = n^{O(1)} زمان استفاده کند؛ بنابراین L یک زیر مجموعه از P است. یکی از مسائل مهم دیگر این است که آیا L=P هست یا نه. می‌دانیم که P=AL است که AL مجموعه مسائل حل شدنی در حافظهٔ لگاریتمی به کمک ماشین تورینگ غیر قطعی می‌باشد. همچنین می‌توان گفت که P نمی‌تواند بزرگتر از فضای پی[۱] باشد که PSPACE دسته‌ای از مساول قابل حل در فضای چند جمله‌ای هستند. اینکه آیا P = PSPACE هم یک مسئلهٔ باز است. به طور خلاصه:

\mbox{L} \subseteq \mbox{AL} = \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACE} \subseteq \mbox{EXPTIME}.

خواص[ویرایش]

الگوریتم‌های چندجمله‌ای برروی عملیات ترکیب بسته هستند. به این معنا که اگر کسی تابعی با زمان چندجمله‌ای بنویسد با این فرض که صدا زدن تابع زمان ثابتی می‌برد و در برنامه‌ای دیگر این توابع به تعداد چند جمله‌ای بار تکرار شوند در کل الگوریتم، از زمان چند جمله‌ای می‌باشد. یکی از نتایج این آنست که کلاس پی برای خود یک کلاس سطح پایین به حساب می‌آید. همچنین یکی از عواملی که باعث می‌شود گفته شود که کلاس پی مستقل از ماشین است همین مورد است. هر ویژگی ماشینی به عنوان مثال دسترسی تصادفی که بتواند در زمان چندجمله‌ای شبیه‌سازی شود، می‌تواند با زمان اجرای چند جمله‌ای ترکیب شود و یک زمان اجرای چند جمله‌ای دیگر برروی ماشینی ابتدایی تر بسازد.

اثبات خالص چند جمله‌ای بودن زمان یک الگوریتم[ویرایش]

بعضی الگوریتم‌ها نشان داده شده‌اند که در زمان چند جمله‌ای حل می‌شوند اما تا به حال برای آنها الگوریتم دقیقی که این کار را انجام بدهد ارایه نشده است. به عنوان مثال تئوری رابرتسون-سیمور[۲] ضمانت می‌کند که یک لیست متناهی از forbidden minorsها وجود دارد که (به طور مثال) مجموعه‌ای از گراف‌ها را که می‌توان برروی یک چنبره نهان کرد دسته بندی می‌کند. علاوه برآن آن دو ثابت کردند که الگوریتمی از

O(n3)

وجود دارد که به وسیله آن می‌توان تصمیم گرفت که یک گراف مینور[۳] مورد نظر را به عنوان یک زیرگراف دارد یا خیر. این امر منجر به این می‌شود که یک اثبات غیر ساختاری ارایه شود که در آن عنوان می‌شود الگوریتمی از زمان چندجمله‌ای وجود دارد که می‌تواند تصمیم بگیرد آیا یک گراف برروی یک چنبره نهان می‌شود یا خیر علی رغم انکه تا به حال هیچ الگوریتم چندجمله‌ای شناخته شده‌ای برای این مساله وجود ندارد.

دسته بندی‌های معادل[ویرایش]

در مبحث پیچیدگی توصیفی پی به عنوان مسائلی توصیف می ود که قابل بیان در FO(LFP) هستند. که عبارت است از کلاس هم‌ارزی منطق مرتبه یک به آن که به آن Leaset fixed Point اضافه شده است. در کتاب immerman's 1999، دربارهٔ پیچیدگی توصیفی، این نتیجه را کار Vardi & Immerman[۴] می‌داند.

منابع[ویرایش]

  1. [۱] PSPACE
  2. [۲] Robertson–Seymour theorem
  3. [۳] Minor (graph theory)
  4. [۴] Immerman-Vardi theorem