บทความน ไม ม การอ างอ งจากแหล งท มาใดกร ณาช วยปร บปร งบทความน โดยเพ มการอ างอ งแหล งท มาท น าเช อถ อ เน อความท ไม ม แหล

กลุ่มความซับซ้อน พี และ เอ็นพี ทฤษฎีความซับซ้อนในการคำนวณเป็นส่วนหนึ่งของทฤษฎีการคำนวณที่ศึกษาเกี่ยวกับทรัพยากรที่ต้องการ สำหรับการแก้ปัญหาหนึ่งๆ ทรัพยากรที่สนใจโดยทั่วไปคือเวลา (ต้องใช้การทำงานกี่ขั้นตอนก่อนจะแก้ปัญหาได้) และเนื้อที่ (ต้องใช้เนื้อที่เท่าใดในการแก้ปัญหา)

รูปแสดงความกลุ่มความซับซ้อนในกรณี P ≠ NP. ถ้า P = NP, P, NP, NP-complete ก็จะกลายเป็นกลุ่มปัญหาเดียวกันนั่นเอง

ในทฤษฎีดังกล่าว กลุ่ม พี (P) คือประกอบไปด้วยปัญหาการตัดสินใจที่สามารถหาคำตอบได้โดยเครื่องจักรเชิงลำดับแบบกำหนด (deterministic sequential machine) ในเวลาที่เป็นพหุนามของขนาดของข้อมูลป้อนเข้า กลุ่มปัญหา เอ็นพี (NP) ประกอบไปด้วยปัญหาการตัดสินใจที่ในกรณีที่คำตอบคือ 'ใช่' สามารถตรวจสอบได้ถ้าให้ข้อมูลที่เหมาะสม หรือพูดในอีกทางหนึ่งที่เหมือนกันว่า เป็นกลุ่มของปัญหาที่สามารถหาคำตอบได้ในบน อาจกล่าวได้ว่าปัญหาเปิดที่สำคัญที่สุดในนั้น เกี่ยวข้องกับความสัมพันธ์ของกลุ่มปัญหาทั้งสองนี้:

P เท่ากับ NP หรือไม่ ?

ในปี 2545 มีการสำรวจความเชื่อของนักวิจัย 100 คน 61 คนเชื่อว่าพีไม่เท่ากับเอ็นพี 9 คนเชื่อว่าเท่ากัน 22 คนตอบว่าไม่แน่ใจ ส่วนที่เหลือเชื่อว่าจะไม่สามารถหาบทพิสูจน์ได้

กลุ่มของปัญหาที่อยู่ในเอ็นพีที่มีความสำคัญและได้รับความสนใจมากที่สุดก็คือกลุ่มของ เอ็นพีบริบูรณ์ ซึ่งเป็นกลุ่มของปัญหาที่ไม่น่าจะอยู่ใน พี มากที่สุด ความสัมพันธ์ของ พี เอ็นพี และ เอ็นพีบริบูรณ์ ที่นักวิจัยเชื่อกันเป็นไปตามรูป ซึ่งจะเห็นได้ว่า ทั้งพีและเอ็นพีบริบูรณ์อยู่ภายใน เอ็นพี แต่ว่าเอ็นพีบริบูรณ์กับพีไม่มีส่วนที่ซ้อนทับกันเลย อีกทั้งยังมีเซ็ตบางเซ็ตที่อยู่ในเอ็นพีแต่อยู่นอกพีและเอ็นพีบริบูรณ์

ปัญหาพีและเอ็นพีสามารถถามได้อีกแบบคือ "ถ้าเรามีปัญหาที่สามารถตรวจคำตอบ (ใช่/ ไม่ใช่) ได้อย่างรวดเร็ว เราจะสามารถหาคำตอบได้อย่างรวดเร็วหรือไม่?" ยกตัวอย่างเช่น ถ้าเราอยากตรวจสอบว่าจำนวนๆหนึ่งเป็นจำนวนประกอบหรือไม่ หากเรามีจำนวน 53308290611 อยู่ แล้วต้องการตรวจสอบ วิธีที่ทำได้วิธีหนึ่งก็คือทดลองจำนวนทุกจำนวนว่าหารจำนวนนี้ลงตัวหรือไม่ แต่วิธีนี้ใช้เวลาการทำงานเป็น exponential เมื่อเทียบกับขนาดของอินพุต (ขนาดของอินพุตในที่นี้ไม่ใช่ค่าของจำนวน แต่เป็นจำนวนของบิตที่ใช้ในการแทนค่าจำนวนนั้น ยกตัวอย่างเช่น จำนวน 128 มีขนาดของอินพุตเท่ากับ 8 เพราะว่า $128={10000000}_{2}$ )