P (پیچیدگی)

زبان L در کلاس P قرار دارد اگر و تنها اگر ماشین تورینگ 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 قرار می‌گیرد.

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

P همچنین معادل L، کلاس مسائل قابل حل در مرتبهٔ حافظهٔ لگاریتمی، در نظر گرفته می‌شود. تصمیم گیرنده‌ای که از ${\displaystyle O(\log n)}$

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

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

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

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

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

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