P (پیچیدگی)

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

تعریف

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

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

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

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

مسائل مهم دستهٔ P

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

ارتباط با کلاس‌های دیگر

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

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

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

خواص

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

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

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

O(n³)

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

دسته بندی‌های معادل

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

جستارهای وابسته

• نظریه پیچیدگی محاسباتی
• پیچیدگی زمانی
• طراحی الگوریتم
• مهندسی الگوریتم
• NP (پیچیدگی)
• الگوریتم ان‌پی-آسان
• ان‌پی سخت
• ان‌پی کامل
• ان-پی کامل قوی

منابع

1. PSPACE
2. Robertson–Seymour theorem
3. Minor (graph theory)
4. Immerman-Vardi theorem