ในทฤษฎีความซับซ้อนของการคำนวณPหรือที่รู้จักกันในชื่อPTIMEหรือDTIME ( n ^O(1) ) เป็นคลาสความซับซ้อน พื้นฐาน ประกอบด้วยปัญหาการตัดสินใจ ทั้งหมด ที่สามารถแก้ไขได้โดยเครื่องจักรทัวริงแบบกำหนดได้โดยใช้เวลาในการคำนวณเป็นจำนวนพหุนามหรือเวลาพหุนาม

วิทยานิพนธ์ของคอบแฮมกล่าวว่า P คือกลุ่มของปัญหาการคำนวณที่ "สามารถแก้ไขได้อย่างมีประสิทธิภาพ" หรือ " จัดการได้ " ข้อสันนิษฐานนี้ไม่แม่นยำนัก เพราะในทางปฏิบัติ ปัญหาบางอย่างที่ไม่ทราบว่าอยู่ในกลุ่ม P กลับมีวิธีแก้ปัญหาที่ใช้ได้จริง และบางปัญหาที่อยู่ในกลุ่ม P กลับไม่มีวิธีแก้ปัญหาที่ใช้ได้จริง แต่หลักการนี้ก็เป็นกฎ ทั่วไป ที่มีประโยชน์

ภาษาLอยู่ใน P ก็ต่อเมื่อมีเครื่องจักรทัวริงเชิงกำหนดMอยู่จริง โดย ที่

• Mใช้เวลาในการประมวลผลแบบพหุนามสำหรับข้อมูลป้อนเข้าทั้งหมด
• สำหรับทุกxในL , Mจะส่งคืนค่า 1
• สำหรับค่าx ทั้งหมด ที่ไม่ได้อยู่ในL M จะ ส่งคืนค่า 0

P สามารถมองได้ว่าเป็นตระกูลวงจรบูลีน ที่เป็นเอกรูปเช่นกัน ภาษาLอยู่ใน P ก็ต่อเมื่อมีตระกูลวงจรบูลีนที่เป็นเอกรูปซึ่งประมวลผลได้ในเวลาพหุนามอยู่จริงโดยที่ ${\displaystyle \{C_{n}:n\in \mathbb {N} \}}$

• สำหรับทุกค่าจะรับข้อมูลnบิตเป็นอินพุตและส่งออก 1 บิต${\displaystyle n\in \mathbb {N} }$${\displaystyle C_{n}}$
• สำหรับทุกxในL ,${\displaystyle C_{|x|}(x)=1}$
• สำหรับx ทุกตัว ที่ไม่อยู่ในL${\displaystyle C_{|x|}(x)=0}$

สามารถลดทอนนิยามของวงจรลงได้โดยใช้เพียง ตระกูล เอกรูปของลอการิทึมสเปซโดยไม่ต้องเปลี่ยนระดับความซับซ้อน

P เป็นที่ทราบกันว่าประกอบด้วยปัญหาธรรมชาติหลายอย่าง รวมถึงเวอร์ชันการตัดสินใจของการเขียนโปรแกรมเชิงเส้นและการค้นหาการจับคู่สูงสุดในปี 2545 ได้มีการแสดงให้เห็นว่าปัญหาในการพิจารณาว่าจำนวนใดเป็นจำนวนเฉพาะ หรือ ไม่ นั้น อยู่ใน P ^{[ 1 ]}กลุ่มปัญหาฟังก์ชัน ที่เกี่ยวข้อง คือFP

ปัญหาธรรมชาติหลายอย่างสมบูรณ์สำหรับ P รวมถึงst-การเชื่อมต่อ (หรือการเข้าถึง ) บนกราฟสลับ^{[ 2 ]}บทความเกี่ยวกับปัญหา P-completeแสดงรายการปัญหาที่เกี่ยวข้องเพิ่มเติมใน P

การขยายความทั่วไปของ P คือNPซึ่งเป็นคลาสของปัญหาการตัดสินใจที่สามารถตัดสินได้โดยเครื่องทัวริงแบบไม่กำหนดที่ทำงานในเวลาพหุนามหรือกล่าวอีกนัยหนึ่งคือ เป็นคลาสของปัญหาการตัดสินใจที่แต่ละกรณี "ใช่" มีใบรับรองขนาดพหุนาม และสามารถตรวจสอบใบรับรองได้โดยเครื่องทัวริงแบบกำหนดที่ทำงานในเวลาพหุนาม คลาสของปัญหาที่เป็นจริงสำหรับกรณี "ไม่" เรียกว่าco-NP P เป็นเซตย่อยของ NP และ co-NP อย่างเห็นได้ชัด ผู้เชี่ยวชาญส่วนใหญ่เชื่อว่าเป็นเซตย่อยที่แท้จริง^{[ 3 ]}แม้ว่าความเชื่อนี้ ( สมมติฐาน) ยังไม่ได้รับการพิสูจน์อีกปัญหาหนึ่งที่ยังเปิดอยู่คือ NP = co-NP หรือไม่ เนื่องจาก P = co-P ^{[ 4 ]}คำตอบเชิงลบจะหมายความว่า ${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$

เป็นที่ทราบกันดีว่า P มีขนาดอย่างน้อยเท่ากับLซึ่งเป็นกลุ่มของปัญหาที่สามารถตัดสินได้ในพื้นที่หน่วยความจำแบบลอการิทึมตัวตัดสินที่ใช้พื้นที่หน่วยความจำไม่สามารถใช้เวลาได้มากกว่าเวลา เพราะนี่คือจำนวนการกำหนดค่าที่เป็นไปได้ทั้งหมด ดังนั้น L จึงเป็นเซตย่อยของ P ปัญหาสำคัญอีกประการหนึ่งคือ L = P หรือไม่ เรารู้ว่า P = AL ซึ่งเป็นเซตของปัญหาที่สามารถแก้ไขได้ในหน่วยความจำแบบลอการิทึมโดยใช้เครื่องทัวริงแบบสลับกัน เป็นที่ทราบกันดีว่า P มีขนาดไม่ใหญ่กว่าPSPACEซึ่งเป็นกลุ่มของปัญหาที่สามารถตัดสินได้ในพื้นที่พหุนาม PSPACE เทียบเท่ากับ NPSPACE ตามทฤษฎีบทของ Savitchอีกครั้ง การที่ P = PSPACE หรือไม่นั้นยังคงเป็นปัญหาที่ยังไม่มีคำตอบ สรุปได้ดังนี้: ${\displaystyle O(\log n)}$${\displaystyle 2^{O(\log n)}=n^{O(1)}}$

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

ในที่นี้EXPTIMEคือกลุ่มของปัญหาที่สามารถแก้ไขได้ในเวลาแบบเลขชี้กำลัง จากกลุ่มทั้งหมดที่แสดงไว้ข้างต้น มีเพียงสองกลุ่มเท่านั้นที่ทราบว่ามีการบรรจุอย่างเข้มงวด:

• P อยู่ภายใน EXPTIME อย่างเคร่งครัด ดังนั้น ปัญหา EXPTIME-hard ทั้งหมดจึงอยู่นอก P และอย่างน้อยหนึ่งในขอบเขตการบรรจุทางด้านขวาของ P ข้างต้นนั้นเข้มงวด (อันที่จริง เป็นที่เชื่อกันอย่างกว้างขวางว่าทั้งสามขอบเขตนั้นเข้มงวด)
• ตัวอักษร L ถูกจำกัดไว้เฉพาะใน PSPACE เท่านั้น

ปัญหาที่ยากที่สุดใน P คือปัญหา P-complete

อีกหนึ่งการขยายความของ P คือP/polyหรือ Nonuniform Polynomial-Time (NP-PP) หากปัญหาอยู่ใน P/poly ปัญหานั้นจะสามารถแก้ไขได้ในเวลาพหุนามแบบกำหนดได้ (deterministic polynomial time) โดยมีเงื่อนไขว่า มี สตริงคำแนะนำที่ขึ้นอยู่กับความยาวของอินพุตเท่านั้น อย่างไรก็ตาม ต่างจาก NP ตรงที่เครื่องจักรเวลาพหุนามไม่จำเป็นต้องตรวจจับสตริงคำแนะนำที่ฉ้อโกง มันไม่ใช่ตัวตรวจสอบความถูกต้อง P/poly เป็นกลุ่มปัญหาขนาดใหญ่ที่ครอบคลุมปัญหาในทางปฏิบัติเกือบทั้งหมด รวมถึงปัญหาBPP ทั้งหมด หาก P/poly ประกอบด้วย NP ลำดับชั้นพหุนามจะยุบตัวลงไปอยู่ที่ระดับที่สอง ในทางกลับกัน มันยังประกอบด้วยปัญหาที่ไม่สามารถนำไปใช้ได้จริงบางอย่าง รวมถึงปัญหาที่ไม่สามารถตัดสินได้บางอย่าง เช่น ปัญหาแบบเอกภาค (unary version) ของปัญหาที่ไม่สามารถตัดสินได้ใดๆ

ในปี พ.ศ. 2542 Jin-Yi Caiและ D. Sivakumar ได้ต่อยอดจากงานของMitsunori Ogiharaและแสดงให้เห็นว่าหากมีภาษาสปาร์สที่ P-complete อยู่จริง L = P ^{[ 5 ]}

P อยู่ภายในBQP ; ยังไม่ทราบแน่ชัดว่าการบรรจุนี้เป็นการบรรจุที่เข้มงวดหรือไม่

อัลกอริทึมแบบใช้เวลาพหุนามนั้นมีคุณสมบัติปิดภายใต้การประกอบ (composition) โดยสัญชาตญาณแล้ว หมายความว่า ถ้าเราเขียนฟังก์ชันที่ใช้เวลาพหุนาม โดยสมมติว่าการเรียกใช้ฟังก์ชันนั้นใช้เวลาคงที่ และถ้าฟังก์ชันที่ถูกเรียกเหล่านั้นเองต้องการเวลาพหุนาม อัลกอริทึมทั้งหมดก็จะใช้เวลาพหุนามเช่นกัน ผลที่ตามมาอย่างหนึ่งก็คือ P มีค่าต่ำสำหรับตัวมันเอง นี่เป็นหนึ่งในเหตุผลหลักที่ทำให้ P ถูกพิจารณาว่าเป็นคลาสที่ไม่ขึ้นกับเครื่องจักร คุณสมบัติใดๆ ของเครื่องจักร เช่นการเข้าถึงแบบสุ่ม (random access ) ที่สามารถจำลองได้ในเวลาพหุนาม ก็สามารถนำมาประกอบกับอัลกอริทึมหลักที่ใช้เวลาพหุนามเพื่อลดทอนให้เป็นอัลกอริทึมที่ใช้เวลาพหุนามบนเครื่องจักรพื้นฐานกว่าได้

ภาษาใน P ยังปิดภายใต้การกลับด้านการตัดกันการรวมการต่อกันการปิดแบบคลีนโฮโมมอร์ฟิซึมผกผันและการเติมเต็ม^{[ 6 ]}

เป็นที่ทราบกันดีว่าปัญหาบางอย่างสามารถแก้ไขได้ในเวลาพหุนาม แต่ยังไม่มีอัลกอริทึมที่เป็นรูปธรรมสำหรับการแก้ปัญหาเหล่านั้น ตัวอย่างเช่นทฤษฎีบทของโรเบิร์ตสัน-เซย์มัวร์รับประกันว่ามีรายการไมเนอร์ต้องห้ามจำนวน จำกัด ที่บ่งบอกลักษณะเฉพาะ (เช่น) เซตของกราฟที่สามารถฝังลงบนทอรัสได้ ยิ่งไปกว่านั้น โรเบิร์ตสันและเซย์มัวร์แสดงให้เห็นว่ามีอัลกอริทึม O( n³ ⁾สำหรับการพิจารณาว่ากราฟหนึ่งมีกราฟที่กำหนดเป็นไมเนอร์หรือไม่ ซึ่งให้การพิสูจน์แบบไม่สร้างสรรค์ว่ามีอัลกอริทึมในเวลาพหุนามสำหรับการพิจารณาว่ากราฟที่กำหนดสามารถฝังลงบนทอรัสได้หรือไม่ แม้ว่าจะไม่มีอัลกอริทึมที่เป็นรูปธรรมสำหรับปัญหานี้ก็ตาม

ในความซับซ้อนเชิงพรรณนา P สามารถอธิบายได้ว่าเป็นปัญหาที่แสดงได้ในFO(LFP)ซึ่ง เป็น ตรรกะลำดับที่หนึ่งที่ มีตัวดำเนินการ จุดคงที่น้อยที่สุดเพิ่มเข้ามา บนโครงสร้างที่มีลำดับ ในตำราของ Immerman ปี 1999 เกี่ยวกับความซับซ้อนเชิงพรรณนา^{[ 7 ]} Immermanอ้างถึงผลลัพธ์นี้ให้กับVardi ^{[ 8 ]}และ Immerman ปี 1982 ^{[ 9 ]}

ในปี พ.ศ. 2535 Bellantoni และCook ได้ให้ลักษณะเฉพาะทางเลือกของ FP ^{[ 10 ]}โดยกำหนดฟังก์ชันที่คำนวณได้ในเวลาพหุนามโดยใช้รูปแบบการเรียกซ้ำที่ปลอดภัย ซึ่งให้คำจำกัดความเชิงโครงสร้างที่ไม่ขึ้นกับเครื่องจักรภายในกรอบของความซับซ้อนในการคำนวณโดยปริยาย^{[ 11 ]}

มีการตีพิมพ์ในปี พ.ศ. 2544 ว่า PTIME สอดคล้องกับไวยากรณ์การเชื่อมต่อช่วง (เชิงบวก) ^{[ 12 ]}

P ยังสามารถกำหนดเป็นคลาสความซับซ้อนของอัลกอริทึมสำหรับปัญหาที่ไม่ใช่ปัญหาการตัดสินใจ^{[ 13 ]} (แม้ว่า ตัวอย่างเช่น การหาคำตอบสำหรับ อินสแตนซ์ 2-satisfiabilityในเวลาพหุนามจะให้อัลกอริทึมพหุนามสำหรับปัญหาการตัดสินใจที่เกี่ยวข้องโดยอัตโนมัติ) ในกรณีนั้น P ไม่ใช่เซตย่อยของ NP แต่เป็น โดยที่คือคลาสของปัญหาการตัดสินใจ ${\displaystyle P\cap DEC}$${\displaystyle DEC}$

Kozen ^{[ 14 ]}ระบุว่าCobhamและEdmonds "โดยทั่วไปได้รับการยกย่องว่าเป็นผู้คิดค้นแนวคิดเรื่องเวลาพหุนาม" แม้ว่าRabinจะคิดค้นแนวคิดนี้ขึ้นมาเองโดยอิสระและในช่วงเวลาเดียวกัน (บทความของ Rabin ^{[ 15 ]}อยู่ในรายงานการประชุมปี 1967 ของการประชุมปี 1966 ในขณะที่บทความของ Cobham ^{[ 16 ]}อยู่ในรายงานการประชุมปี 1965 ของการประชุมปี 1964 และบทความของ Edmonds ^{[ 17 ]}ได้รับการตีพิมพ์ในวารสารในปี 1965 แม้ว่า Rabin จะไม่ได้กล่าวถึงบทความใดเลยและดูเหมือนจะไม่ทราบเกี่ยวกับบทความเหล่านั้น) ^{[ 18 ]} Cobham คิดค้นคลาสนี้ขึ้นมาเพื่อเป็นวิธีที่แข็งแกร่งในการกำหนดลักษณะของอัลกอริทึมที่มีประสิทธิภาพ ซึ่งนำไปสู่วิทยานิพนธ์ของ Cobhamอย่างไรก็ตามHC Pocklingtonในบทความปี 1910 ^{[ 19 ] [ 20 ]}ได้วิเคราะห์อัลกอริทึมสองแบบสำหรับการแก้ปัญหาความสอดคล้องกำลังสอง และสังเกตว่าอัลกอริทึมหนึ่งใช้เวลา "เป็นสัดส่วนกับกำลังของลอการิทึมของค่าสัมบูรณ์" และเปรียบเทียบกับอัลกอริทึมที่ใช้เวลาเป็นสัดส่วน "กับค่าสัมบูรณ์เองหรือรากที่สองของมัน" จึงแยกความแตกต่างอย่างชัดเจนระหว่างอัลกอริทึมที่ทำงานในเวลาพหุนามกับอัลกอริทึมที่ทำงานในเวลาเลขชี้กำลัง (ปานกลาง)

• บทความเรื่อง "ทฤษฎีความซับซ้อนเชิงคำนวณ"โดย วอลเตอร์ ดีน ในสารานุกรมปรัชญาแห่งมหาวิทยาลัยสแตนฟอร์ด ฤดูใบไม้ ร่วง ปี 2021
• StackOverflow. "ทฤษฎีความซับซ้อน - ทำไม co-P ถึงเท่ากับ P" . Stack Overflow . สืบค้นเมื่อ15 พฤศจิกายน 2025 .
• Complexity Zoo :คลาส P
• Complexity Zoo : Class P/poly