ปัญหา P เทียบกับ NP เป็น ปัญหาสำคัญ ที่ยังแก้ไม่ตก ในวิทยาการคอมพิวเตอร์เชิงทฤษฎีโดยคร่าวๆ แล้ว ปัญหานี้คือ ทุกปัญหาที่สามารถตรวจสอบคำตอบได้อย่างรวดเร็ว จะสามารถหาคำตอบได้อย่างรวดเร็วเช่นกันหรือไม่

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

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

ปัญหานี้ได้รับการขนานนามว่าเป็นปัญหาเปิดที่สำคัญที่สุดในวิทยาศาสตร์คอมพิวเตอร์ [ ^{2 ] นอกเหนือ}จากการเป็นปัญหาสำคัญในทฤษฎีการคำนวณแล้วการพิสูจน์ไม่ว่าจะทางใดทางหนึ่งก็จะมีนัยสำคัญอย่างลึกซึ้งต่อคณิตศาสตร์ การเข้ารหัสการวิจัยอั ลกอริทึม ปัญญาประดิษฐ์ทฤษฎีเกมการประมวลผลมัลติมีเดียปรัชญาเศรษฐศาสตร์และสาขาอื่นๆ อีกมากมาย^{[ 3 ]}ปัญหา นี้เป็นหนึ่งในเจ็ดปัญหา Millennium Prize Problemsที่ได้รับการคัดเลือกโดยClay Mathematics Instituteซึ่งแต่ละปัญหามีรางวัล 1,000,000 ดอลลาร์สหรัฐสำหรับคำตอบที่ถูกต้องครั้งแรก

พิจารณาปัญหาใช่/ไม่ใช่ต่อไปนี้: กำหนด ตาราง ซูโดกุ ที่ไม่สมบูรณ์ ขนาด${\displaystyle n^{2}\times n^{2}}$มีวิธีแก้ปัญหาทางกฎหมายอย่างน้อยหนึ่งวิธีหรือไม่ ที่ทุกแถว ทุกคอลัมน์ และ${\displaystyle n\times n}$ตารางประกอบด้วยจำนวนเต็ม 1 ถึง 3${\displaystyle n^{2}}$การตรวจสอบคำตอบ "ใช่" ของปัญหาซูโดกุแบบทั่วไปนี้ทำได้ง่ายเมื่อมีคำตอบที่เป็นไปได้อยู่แล้ว อย่างไรก็ตาม ยังไม่เป็นที่ทราบแน่ชัดว่ามีอัลกอริทึมแบบใช้เวลาในการคำนวณแบบพหุนามที่สามารถตอบคำถาม "ใช่" หรือ "ไม่" ได้อย่างถูกต้องสำหรับทุกกรณีของปัญหานี้หรือไม่ ดังนั้น ซูโดกุแบบทั่วไปจึงอยู่ในกลุ่ม NP (ตรวจสอบได้อย่างรวดเร็ว) แต่อาจจะอยู่ในกลุ่ม P (แก้ไขได้อย่างรวดเร็ว) หรือไม่ก็ได้ (จำเป็นต้องพิจารณาซูโดกุแบบทั่วไป เนื่องจากซูโดกุที่มีขนาดคงที่ใดๆ จะมีจำนวนตารางที่เป็นไปได้จำกัดเท่านั้น ในกรณีนี้ ปัญหาจะอยู่ในกลุ่ม P เนื่องจากสามารถหาคำตอบได้โดยการค้นหาในตาราง)

การระบุปัญหา P เทียบกับ NP อย่างแม่นยำได้รับการนำเสนอในปี พ.ศ. 2514 โดยStephen Cookในบทความสำคัญของเขาเรื่อง "ความซับซ้อนของขั้นตอนการพิสูจน์ทฤษฎีบท" ^{[ 4 ]}และโดยLeonid Levin อย่างอิสระ ในปี พ.ศ. 2516 ^{[ 5 ]}

แม้ว่าปัญหา P เทียบกับ NP จะได้รับการกำหนดอย่างเป็นทางการในปี 1971 แต่ก็มีลางสังหรณ์เกี่ยวกับปัญหาพื้นฐานที่เกี่ยวข้องมาก่อนหน้านี้แล้ว ในปี 1955 นักคณิตศาสตร์John Nashได้เขียนจดหมายถึงสำนักงานความมั่นคงแห่งชาติโดยคาดการณ์ว่าเวลาที่ต้องใช้ในการถอดรหัสที่ซับซ้อนเพียงพอจะเพิ่มขึ้นแบบทวีคูณตามความยาวของกุญแจ^{[ 6 ]}หากพิสูจน์ได้^{[หมายเหตุ 2 ]}สิ่งนี้จะหมายถึงสิ่งที่ปัจจุบันเรียกว่า P  ≠  NP เนื่องจากกุญแจที่เสนอสามารถตรวจสอบได้ในเวลาพหุนาม ในจดหมายที่เขียนโดยKurt GödelถึงJohn von Neumann ในปี 1956 Gödel ถามว่าการพิสูจน์ทฤษฎีบท (ซึ่งปัจจุบันทราบกันว่าเป็นco-NP-complete ) สามารถแก้ไขได้ในเวลากำลังสองหรือ เชิงเส้นหรือไม่ และตั้งสมมติฐานว่าหากเป็นเช่นนั้น การค้นพบการพิสูจน์ทางคณิตศาสตร์ก็จะสามารถทำให้เป็นอัตโนมัติได้^{[ 7 ]}

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

ในการวิเคราะห์ดังกล่าว จำเป็นต้องมีแบบจำลองของคอมพิวเตอร์ที่ต้องนำมาวิเคราะห์เวลา โดยทั่วไปแบบจำลองเหล่านี้จะถือว่าคอมพิวเตอร์เป็นแบบกำหนดได้ (เมื่อกำหนดสถานะปัจจุบันของคอมพิวเตอร์และข้อมูลป้อนเข้าแล้ว จะมีเพียงการกระทำเดียวที่เป็นไปได้ที่คอมพิวเตอร์อาจทำได้) และเป็นแบบลำดับ (มันดำเนินการทีละอย่าง)

ในทฤษฎีนี้ คลาส P ประกอบด้วยปัญหาการตัดสินใจ ทั้งหมด (ที่กำหนดไว้ด้านล่าง ) ที่สามารถแก้ไขได้บนเครื่องลำดับแบบกำหนดได้ในระยะเวลาที่เป็นพหุนามตามขนาดของอินพุต คลาสNPประกอบด้วยปัญหาการตัดสินใจทั้งหมดที่มีคำตอบเชิงบวกที่สามารถตรวจสอบได้ในเวลาพหุนามเมื่อได้รับข้อมูลที่ถูกต้อง หรือเทียบเท่ากับคำตอบที่สามารถหาได้ในเวลาพหุนามบนเครื่องที่ไม่ใช่แบบกำหนดได้^{[ 8 ]}เห็นได้ชัดว่า P ⊆ NP อาจกล่าวได้ว่าคำถามเปิดที่ใหญ่ที่สุดในวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีเกี่ยวข้องกับความสัมพันธ์ระหว่างสองคลาสนี้

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

ตั้งแต่ปี 2001 วิลเลียม กาซาร์ชได้ทำการสำรวจความคิดเห็นของนักวิจัย 3 ครั้งเกี่ยวกับ P  ≠  NP และคำถามที่เกี่ยวข้อง^{[ 9 ] [ 10 ] [ 11 ]}สัดส่วนของผู้ตอบแบบสอบถามที่เชื่อว่า P  ≠  NP คือ 61% ในปี 2001 ^{[หมายเหตุ 3 ]} 83% ในปี 2011 และ 88% ในปี 2018 โดยมีผู้ตอบแบบสอบถาม 100, 151 และ 124 คน ตามลำดับ^{[ 11 ]}เมื่อจำกัดเฉพาะผู้เชี่ยวชาญ ผู้ตอบแบบสอบถามในปี 2018 จำนวน 99% เชื่อว่า P  ≠  NP ^{[ 11 ]}การสำรวจเหล่านี้ไม่ได้หมายความว่า P  =  NP; ดังที่กาซาร์ชกล่าวไว้ว่า: "สิ่งนี้ไม่ได้ทำให้เราเข้าใกล้การแก้ปัญหา P=?NP หรือรู้ว่าเมื่อใดจะได้รับการแก้ไข แต่เป็นการพยายามรายงานอย่างเป็นกลางเกี่ยวกับความคิดเห็นส่วนตัวของยุคนี้" ^{[ 9 ]}

ในการแก้ปัญหา P  =  NP นั้น แนวคิดเรื่อง NP-completeness มีประโยชน์มาก ปัญหา NP-complete คือปัญหาที่สามารถลดรูปไปเป็นปัญหา NP อื่นๆ ได้ในเวลาพหุนาม และยังสามารถตรวจสอบคำตอบได้ในเวลาพหุนาม กล่าวคือ ปัญหา NP ใดๆ ก็สามารถแปลงเป็นปัญหา NP-complete ใดๆ ก็ได้ โดยทั่วไปแล้ว ปัญหา NP-complete คือปัญหา NP ที่มีความ "ยาก" อย่างน้อยก็เท่ากับปัญหาอื่นๆ ใน NP

ปัญหา NP-hardคือปัญหาที่ยากอย่างน้อยเท่ากับปัญหา NP กล่าวคือ ปัญหา NP ทั้งหมดสามารถลดรูป (ในเวลาพหุนาม) ไปเป็นปัญหา NP-hard ได้ ปัญหา NP-hard ไม่จำเป็นต้องอยู่ในกลุ่มปัญหา NP กล่าวคือ ไม่จำเป็นต้องมีคำตอบที่ตรวจสอบได้ในเวลาพหุนาม

ตัวอย่างเช่นปัญหาความน่าพอใจของบูลีน (Boolean satisfiability problem)เป็นปัญหา NP-complete ตามทฤษฎีบท Cook–Levinดังนั้นปัญหาใดๆในกลุ่ม NP สามารถแปลงเป็นปัญหาความน่าพอใจของบูลีนได้โดยอัตโนมัติในเวลาพหุนาม ปัญหาความน่าพอใจของบูลีนเป็นหนึ่งในปัญหา NP-complete จำนวนมาก หากปัญหา NP-complete ใดๆ อยู่ในกลุ่ม P ก็จะสรุปได้ว่า P  =  NP อย่างไรก็ตาม ปัญหาสำคัญหลายปัญหาเป็นปัญหา NP-complete และยังไม่มีอัลกอริทึมที่รวดเร็วสำหรับปัญหาเหล่านั้น

จากคำจำกัดความเพียงอย่างเดียว ดูเหมือนว่าปัญหา NP-complete จะไม่สมเหตุสมผล อย่างไรก็ตาม ปัญหา NP-complete ที่ไม่ซับซ้อนสามารถกำหนดได้ดังนี้: เมื่อกำหนดเครื่องทัวริงMที่รับประกันว่าจะหยุดในเวลาพหุนาม มีอินพุตขนาดพหุนามที่Mจะยอมรับหรือไม่? ^{[ 12 ]}ปัญหานี้อยู่ใน NP เพราะ (เมื่อกำหนดอินพุต) การตรวจสอบว่าMยอมรับอินพุตหรือไม่โดยการจำลองM นั้นทำได้ง่าย ปัญหานี้อยู่ใน NP-complete เพราะตัวตรวจสอบสำหรับอินสแตนซ์เฉพาะของปัญหาใน NP สามารถเข้ารหัสเป็นเครื่องM ในเวลาพหุนาม ที่รับโซลูชันที่จะตรวจสอบเป็นอินพุต จากนั้นคำถามที่ว่าอินสแตนซ์นั้นเป็นอินสแตนซ์ใช่หรือไม่ใช่จะถูกกำหนดโดยว่ามีอินพุตที่ถูกต้องอยู่หรือไม่

ปัญหาธรรมชาติข้อแรกที่ได้รับการพิสูจน์ว่าเป็น NP-complete คือปัญหาความพึงพอใจของบูลีน หรือที่รู้จักกันในชื่อ SAT ดังที่กล่าวไว้ข้างต้น นี่คือทฤษฎีบท Cook–Levin การพิสูจน์ว่าความพึงพอใจเป็น NP-complete นั้นมีรายละเอียดทางเทคนิคเกี่ยวกับเครื่องจักรทัวริงที่เกี่ยวข้องกับนิยามของ NP อย่างไรก็ตาม หลังจากที่พิสูจน์ได้ว่าปัญหานี้เป็น NP-complete แล้วการพิสูจน์โดยการลดรูปได้ให้วิธีที่ง่ายกว่าในการแสดงให้เห็นว่าปัญหาอื่นๆ อีกมากมายก็เป็น NP-complete เช่นกัน รวมถึงเกมซูโดกุที่กล่าวถึงก่อนหน้านี้ ในกรณีนี้ การพิสูจน์แสดงให้เห็นว่าวิธีแก้ปัญหาซูโดกุในเวลาพหุนามสามารถใช้ในการเติมตารางละตินในเวลาพหุนาม ได้เช่นกัน ^{[ 13 ]} ซึ่งจะ นำไปสู่วิธีแก้ปัญหาการแบ่งกราฟสามส่วนออกเป็นรูปสามเหลี่ยม^{[ 14 ]}ซึ่งสามารถนำมาใช้ในการหาคำตอบสำหรับกรณีพิเศษของ SAT ที่เรียกว่า 3-SAT ^{[ 15 ]}ซึ่งจะนำไปสู่วิธีแก้ปัญหาความพึงพอใจของบูลีนทั่วไป ดังนั้น วิธีแก้ปัญหาซูโดกุในเวลาพหุนามจึงนำไปสู่วิธีแก้ปัญหาความน่าพอใจในเวลาพหุนามโดยผ่านการแปลงเชิงกลหลายขั้นตอน ซึ่งในทางกลับกันสามารถนำไปใช้แก้ปัญหา NP อื่นๆ ในเวลาพหุนามได้ การใช้การแปลงแบบนี้ทำให้ปัญหาที่ดูเหมือนไม่เกี่ยวข้องกันจำนวนมากสามารถลดรูปไปเป็นปัญหาเดียวกันได้ และในแง่หนึ่งก็คือ "ปัญหาเดียวกัน"

แม้ว่าจะไม่ทราบแน่ชัดว่า P  =  NP หรือไม่ แต่ปัญหาที่อยู่นอกเหนือ P นั้นเป็นที่ทราบกันดี เช่นเดียวกับที่คลาส P ถูกกำหนดในแง่ของเวลาการทำงานแบบพหุนาม คลาสEXPTIMEก็คือเซตของปัญหาการตัดสินใจทั้งหมดที่มี เวลาการทำงาน แบบเลขชี้กำลังกล่าวอีกนัยหนึ่ง ปัญหาใดๆ ใน EXPTIME สามารถแก้ไขได้โดยเครื่องจักรทัวริงแบบกำหนดได้ใน เวลา O (2p ^{( n ) )}โดยที่p ( n ) เป็นฟังก์ชันพหุนามของnปัญหาการตัดสินใจจะสมบูรณ์ใน EXPTIMEหากอยู่ใน EXPTIME และทุกปัญหาใน EXPTIME สามารถลดรูปหลายต่อหนึ่งได้ในเวลาพหุนาม ปัญหาจำนวนหนึ่งเป็นที่ทราบกันว่าสมบูรณ์ใน EXPTIME เนื่องจากสามารถแสดงได้ว่า P  ≠  EXPTIME ปัญหาเหล่านี้จึงอยู่นอก P และดังนั้นจึงต้องใช้เวลามากกว่าพหุนาม ในความเป็นจริง ตามทฤษฎีบทลำดับชั้นของเวลา ปัญหาเหล่านี้ ไม่สามารถแก้ไขได้ในเวลาที่น้อยกว่าเลขชี้กำลังอย่างมีนัยสำคัญ ตัวอย่างเช่น การค้นหากลยุทธ์ที่สมบูรณ์แบบสำหรับ ตำแหน่ง หมากรุกบนกระดานN × N ^{[ 16 ]}และปัญหาที่คล้ายกันสำหรับเกมกระดานอื่นๆ^{[ 17 ]}

ปัญหาในการตัดสินความจริงของข้อความในเลขคณิตของ Presburgerต้องใช้เวลามากขึ้นไปอีกFischerและRabinพิสูจน์ในปี 1974 ^{[ 18 ]}ว่าอัลกอริทึมทุกตัวที่ตัดสินความจริงของข้อความ Presburger ที่มีความยาวnมีเวลาทำงานอย่างน้อย${\displaystyle 2^{2^{cn}}}$สำหรับค่าคงที่c บางค่า ดังนั้นจึงทราบกันดีว่าปัญหานี้ต้องการเวลาในการทำงานมากกว่าแบบเลขชี้กำลัง ยิ่งไปกว่านั้นปัญหาที่ไม่สามารถตัดสินได้เช่นปัญหาการหยุด ทำงาน ยิ่งยากกว่า ปัญหาเหล่านี้ไม่สามารถแก้ไขได้อย่างสมบูรณ์ด้วยอัลกอริทึมใดๆ ในแง่ที่ว่าสำหรับอัลกอริทึมใดๆ ก็ตาม จะมีอย่างน้อยหนึ่งอินพุตที่อัลกอริทึมนั้นจะไม่ให้คำตอบที่ถูกต้อง มันอาจจะให้คำตอบที่ผิด จบลงโดยไม่ให้คำตอบที่แน่ชัด หรือทำงานไปเรื่อยๆ โดยไม่ให้คำตอบใดๆ เลย

นอกจากนี้ยังสามารถพิจารณาคำถามอื่นๆ นอกเหนือจากปัญหาการตัดสินใจได้อีกด้วย หนึ่งในกลุ่มดังกล่าว ซึ่งประกอบด้วยปัญหาการนับ เรียกว่า#P : ในขณะที่ปัญหา NP ถามว่า "มีคำตอบหรือไม่" ปัญหา #P ที่สอดคล้องกันจะถามว่า "มีคำตอบกี่คำตอบ" เห็นได้ชัดว่าปัญหา #P ต้องยากอย่างน้อยเท่ากับปัญหา NP ที่สอดคล้องกัน เนื่องจากจำนวนคำตอบจะบอกได้ทันทีว่ามีคำตอบอย่างน้อยหนึ่งคำตอบหรือไม่ หากจำนวนมากกว่าศูนย์ น่าประหลาดใจที่ปัญหา #P บางปัญหาที่เชื่อว่ายากนั้นสอดคล้องกับปัญหา P ที่ง่าย (เช่น ปัญหาที่ใช้เวลาเชิงเส้น) ^{[ 19 ]}สำหรับปัญหาเหล่านี้ การบอกว่ามีคำตอบหรือไม่นั้นง่ายมาก แต่การบอกว่ามีกี่คำตอบนั้นยากมาก ปัญหาเหล่านี้จำนวนมากเป็น#P-completeและด้วยเหตุนี้จึงเป็นหนึ่งในปัญหาที่ยากที่สุดใน #P เนื่องจากวิธีแก้ปัญหาแบบใช้เวลาพหุนามสำหรับปัญหาใดๆ ก็ตามจะทำให้สามารถแก้ปัญหา #P อื่นๆ ทั้งหมดแบบใช้เวลาพหุนามได้เช่นกัน

ในปี พ.ศ. 2518 Richard E. Ladnerแสดงให้เห็นว่าหาก P  ≠  NP จะมีปัญหาใน NP ที่ไม่อยู่ใน P หรือ NP-complete ^{[ 20 ]}ปัญหาดังกล่าวเรียกว่าปัญหา NP-intermediate ปัญหาไอโซมอร์ฟิซึมของกราฟ ปัญหาลอการิทึม แบบไม่ต่อเนื่องและปัญหาการแยกตัวประกอบจำนวนเต็มเป็นตัวอย่างของปัญหาที่เชื่อว่าเป็น NP-intermediate ปัญหาเหล่านี้เป็นปัญหา NP เพียงไม่กี่ปัญหาที่ไม่ทราบว่าอยู่ใน P หรือเป็น NP-complete

ปัญหาความเหมือนกันของกราฟเป็นปัญหาการคำนวณในการพิจารณาว่ากราฟ จำกัดสองกราฟ มีความเหมือนกันหรือไม่ ปัญหาสำคัญที่ยังไม่ได้รับการแก้ไขในทฤษฎีความซับซ้อนคือปัญหาความเหมือนกันของกราฟอยู่ในระดับ P, NP-complete หรือ NP-intermediate คำตอบยังไม่เป็นที่ทราบแน่ชัด แต่เชื่อกันว่าปัญหานี้อย่างน้อยก็ไม่ใช่ NP-complete ^{[ 21 ]}หากความเหมือนกันของกราฟเป็น NP-complete ลำดับชั้นเวลาพหุนามจะยุบตัวลงสู่ระดับที่สอง^{[ 22 ]}เนื่องจากเป็นที่เชื่อกันอย่างกว้างขวางว่าลำดับชั้นพหุนามไม่ยุบตัวลงสู่ระดับจำกัดใดๆ จึงเชื่อว่าความเหมือนกันของกราฟไม่ใช่ NP-complete อัลกอริทึมที่ดีที่สุดสำหรับปัญหานี้ ซึ่งพัฒนาโดยLászló Babaiทำงานในเวลากึ่งพหุนาม^{[ 23 ]}

ปัญหาการแยกตัวประกอบจำนวนเต็มคือปัญหาการคำนวณในการหาตัวประกอบเฉพาะของจำนวนเต็มที่กำหนดให้ กล่าวอีกนัยหนึ่งคือปัญหาการตัดสินใจว่าอินพุตมีตัวประกอบน้อยกว่าkหรือไม่ ยังไม่มีอัลกอริทึมการแยกตัวประกอบจำนวนเต็มที่มีประสิทธิภาพเป็นที่รู้จัก และข้อเท็จจริงนี้เป็นพื้นฐานของระบบการเข้ารหัสสมัยใหม่หลายระบบ เช่น อัลกอริทึม RSAปัญหาการแยกตัวประกอบจำนวนเต็มอยู่ใน NP และco-NP (และแม้แต่ในUPและ co-UP ^{[ 24 ]} ) หากปัญหานี้เป็น NP-complete ลำดับชั้นเวลาพหุนามจะยุบตัวลงสู่ระดับแรก (เช่น NP = co-NP) อัลกอริทึม ที่มีประสิทธิภาพที่สุดที่รู้จักสำหรับการแยกตัวประกอบจำนวนเต็มคือตะแกรงฟิลด์จำนวนทั่วไปซึ่งใช้เวลาที่คาดหวัง

${\displaystyle O\left(\exp \left(\left({\tfrac {64n}{9}}\log(2)\right)^{\frac {1}{3}}\left(\log(n\log(2))\right)^{\frac {2}{3}}\right)\right)}$

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

การอภิปรายทั้งหมดข้างต้นตั้งอยู่บนสมมติฐานที่ว่า P หมายถึง "ง่าย" และ "ไม่อยู่ใน P" หมายถึง "ยาก" ซึ่งเป็นสมมติฐานที่เรียกว่าทฤษฎีบทของคอบแฮม (Cobham's thesis ) เป็นสมมติฐานที่พบได้ทั่วไปในทฤษฎีความซับซ้อน แต่ก็มีข้อควรระวังอยู่บ้าง

ประการแรก ในทางปฏิบัติอาจไม่ถูกต้อง อัลกอริทึมพหุนามเชิงทฤษฎีอาจมีปัจจัยคงที่หรือเลขชี้กำลังขนาดใหญ่มาก ทำให้ไม่สามารถนำไปใช้ได้จริง ตัวอย่างเช่น ปัญหาของการตัดสินใจว่ากราฟGมีHเป็นไมเนอร์ หรือ ^ไม่โดยที่Hถูกกำหนดไว้ สามารถแก้ไขได้ในเวลาทำงานO ( n² ⁾ [ ^{26 ]}โดยที่nคือจำนวนจุดยอดในGอย่างไรก็ตามสัญกรณ์ O ขนาดใหญ่ซ่อนค่าคงที่ที่ขึ้นอยู่กับH อย่าง มาก ค่าคงที่นี้มากกว่า${\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}$(โดยใช้^{สัญลักษณ์}ลูกศรขึ้นของ Knuth ) และhคือจำนวนจุดยอดในH [ ^{27 ]}

ในทางกลับกัน แม้ว่าปัญหาจะถูกแสดงให้เห็นว่าเป็น NP-complete และแม้ว่า P  ≠  NP ก็อาจยังมีวิธีการที่มีประสิทธิภาพในการแก้ปัญหาในทางปฏิบัติได้ มีอัลกอริธึมสำหรับปัญหา NP-complete จำนวนมาก เช่นปัญหา knapsackปัญหาtraveling salesmanและปัญหา Boolean satisfiabilityที่สามารถแก้ปัญหาตัวอย่างในโลกแห่งความเป็นจริงจำนวนมากได้อย่างเหมาะสมในเวลาที่สมเหตุสมผลความซับซ้อนโดยเฉลี่ยเชิง ประจักษ์ (เวลาเทียบกับขนาดของปัญหา) ของอัลกอริธึมดังกล่าวอาจต่ำอย่างน่าประหลาดใจ ตัวอย่างเช่นอัลกอริธึม simplexในการเขียนโปรแกรมเชิงเส้นซึ่งทำงานได้ดีอย่างน่าประหลาดใจในทางปฏิบัติ แม้ว่าจะมีเวลาซับซ้อน ในกรณีที่เลวร้ายที่สุดแบบเลขชี้กำลัง แต่ก็ทำงานได้เทียบเท่ากับอัลกอริธึมเวลาพหุนามที่ดีที่สุดที่รู้จัก^{[ 28 ]}

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

Cook ได้นำเสนอการทบทวนปัญหาในThe P Versus NP Problem อีกครั้ง ในหัวข้อ "P  =  NP หรือไม่?" ^{[ 29 ]}จากผลสำรวจ^{[ 9 ] [ 30 ]}นักวิทยาศาสตร์คอมพิวเตอร์ส่วนใหญ่เชื่อว่า P  ≠  NP เหตุผลสำคัญประการหนึ่งสำหรับความเชื่อนี้คือ หลังจากศึกษาปัญหาเหล่านี้มานานหลายทศวรรษ ไม่มีใครสามารถหาอัลกอริทึมแบบพหุนามไทม์สำหรับปัญหา NP-complete ที่สำคัญมากกว่า 3,000 ปัญหา (ดูรายชื่อปัญหา NP-complete ) อัลกอริทึมเหล่านี้ถูกค้นหามานานก่อนที่แนวคิดเรื่อง NP-completeness จะถูกกำหนดขึ้นด้วยซ้ำ ( ปัญหา NP-complete 21 ข้อของ Karpซึ่งเป็นหนึ่งในปัญหาแรกๆ ที่พบ ล้วนเป็นปัญหาที่มีอยู่แล้วซึ่งเป็นที่รู้จักกันดีในขณะที่แสดงให้เห็นว่าเป็น NP-complete) ยิ่งไปกว่านั้น ผลลัพธ์ P  =  NP จะหมายถึงผลลัพธ์ที่น่าตกใจอื่นๆ อีกมากมายที่ปัจจุบันเชื่อว่าเป็นเท็จ เช่น NP  = co-NPและP = PH   

นอกจากนี้ ยังมีการโต้แย้งโดยสัญชาตญาณว่าการมีอยู่ของปัญหาที่ยากต่อการแก้ไขแต่สามารถตรวจสอบวิธีแก้ปัญหาได้ง่ายนั้นสอดคล้องกับประสบการณ์ในโลกแห่งความเป็นจริง^{[ 31 ]}

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

ในทางกลับกัน นักวิจัยบางคนเชื่อว่าการเชื่อว่า P  ≠  NP เป็นการมั่นใจมากเกินไป และนักวิจัยควรสำรวจหาหลักฐานของ P  =  NP ด้วย ตัวอย่างเช่น ในปี 2545 มีการกล่าวข้อความเหล่านี้: ^{[ 9 ]}

ข้อโต้แย้งหลักที่สนับสนุนว่า P  ≠  NP คือการขาดความก้าวหน้าพื้นฐานอย่างสิ้นเชิงในด้านการค้นหาแบบครบถ้วน ในความเห็นของผม นี่เป็นข้อโต้แย้งที่อ่อนมาก พื้นที่ของอัลกอริทึมนั้นกว้างใหญ่มาก และเราเพิ่งเริ่มต้นการสำรวจเท่านั้น [...] การแก้ทฤษฎีบทสุดท้ายของแฟร์มาต์ยังแสดงให้เห็นว่าคำถามง่ายๆ อาจได้รับการแก้ไขได้ด้วยทฤษฎีที่ลึกซึ้งมากเท่านั้น

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

หนึ่งในเหตุผลที่ปัญหานี้ดึงดูดความสนใจอย่างมากคือผลที่ตามมาของคำตอบที่เป็นไปได้ ไม่ว่าคำตอบจะไปในทิศทางใดก็ล้วนแต่จะช่วยพัฒนาทฤษฎีอย่างมหาศาล และอาจมีผลกระทบอย่างมากในทางปฏิบัติด้วยเช่นกัน

พี = เอ็นพี

การพิสูจน์ว่า P  =  NP อาจส่งผลกระทบในทางปฏิบัติอย่างน่าทึ่ง หากการพิสูจน์นั้นนำไปสู่วิธีการที่มีประสิทธิภาพในการแก้ปัญหาสำคัญบางอย่างในกลุ่ม NP ผลกระทบที่อาจเกิดขึ้นนั้นมีทั้งด้านบวกและด้านลบ เนื่องจากปัญหา NP-complete ต่างๆ เป็นพื้นฐานในหลายสาขา

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

วิธีแก้ปัญหาที่แสดงให้เห็นว่า P  =  NP อาจพลิกโฉมวงการการเข้ารหัสซึ่งอาศัยความยากของปัญหาบางอย่าง วิธีแก้ปัญหาที่สร้างสรรค์และมีประสิทธิภาพ^{[หมายเหตุ 4 ]}สำหรับปัญหา NP-complete เช่น3-SATจะทำลายระบบการเข้ารหัสที่มีอยู่ส่วนใหญ่ รวมถึง:

• การใช้งาน การเข้ารหัสแบบกุญแจสาธารณะที่มีอยู่[ ^{33 ] เป็นพื้นฐานสำหรับแอปพลิเคชันด้านความปลอดภัยสมัยใหม่ หลาย}อย่าง เช่น ธุรกรรมทางการเงินที่ปลอดภัยบนอินเทอร์เน็ต
• รหัสลับแบบสมมาตรเช่นAESหรือ3DES [ ^{34 ] ใช้สำหรับการ เข้ารหัส}ข้อมูลการสื่อสาร
• การแฮชแบบเข้ารหัสลับซึ่งเป็นพื้นฐานของสกุลเงินดิจิทัลบล็อกเชนเช่นบิตคอยน์และใช้ในการตรวจสอบความถูกต้องของการอัปเดตซอฟต์แวร์ สำหรับแอปพลิเคชันเหล่านี้ การค้นหาภาพก่อนหน้าที่แฮชเป็นค่าที่กำหนดจะต้องยาก โดยในอุดมคติแล้วควรใช้เวลาแบบเลขชี้กำลัง หาก P  =  NP ก็สามารถใช้เวลาแบบพหุนามได้ โดยการลดรูปเป็น SAT ^{[ 35 ]}

จำเป็นต้องมีการปรับเปลี่ยนหรือแทนที่โซลูชันเหล่านี้ด้วย โซลูชัน ที่มีความปลอดภัยทางทฤษฎีสารสนเทศซึ่งไม่ถือว่า P  ≠  NP

นอกจากนี้ ยังมีประโยชน์มหาศาลที่จะตามมาจากการทำให้ปัญหาที่ปัจจุบันแก้ไม่ได้ทางคณิตศาสตร์หลายอย่างสามารถแก้ไขได้ ตัวอย่างเช่น ปัญหาหลายอย่างในการวิจัยการดำเนินงานเป็น NP-complete เช่นการเขียนโปรแกรมจำนวนเต็มบาง ประเภท และปัญหาพนักงานขายเดินทางการแก้ปัญหาเหล่านี้อย่างมีประสิทธิภาพจะมีผลกระทบอย่างมากต่อโลจิสติกส์ ปัญหาสำคัญอื่นๆ อีกมากมาย เช่น ปัญหาบางอย่างในการทำนายโครงสร้างโปรตีนก็เป็น NP-complete เช่นกัน^{[ 36 ]}การทำให้ปัญหาเหล่านี้สามารถแก้ไขได้อย่างมีประสิทธิภาพจะช่วยพัฒนาวิทยาศาสตร์ชีวภาพและเทคโนโลยีชีวภาพได้อย่างมาก

การเปลี่ยนแปลงเหล่านี้อาจไม่มีนัยสำคัญเมื่อเทียบกับการปฏิวัติที่การแก้ปัญหา NP-complete อย่างมีประสิทธิภาพจะก่อให้เกิดในคณิตศาสตร์เอง Gödel ในความคิดแรกเริ่มของเขาเกี่ยวกับความซับซ้อนของการคำนวณ ได้กล่าวไว้ว่าวิธีการเชิงกลที่สามารถแก้ปัญหาใดๆ ก็ได้จะปฏิวัติวงการคณิตศาสตร์: ^{[ 37 ] [ 38 ]}

หากมีเครื่องจักรที่มี φ( n ) ∼ k ⋅ n (หรือแม้แต่ ∼ k ⋅ n ² ) จริงๆ สิ่งนี้จะส่งผลสำคัญอย่างยิ่ง กล่าวคือ นั่นหมายความว่าถึงแม้ปัญหาการตัดสินใจ (Entscheidungsproblem) จะไม่สามารถตัดสิน ได้ แต่การทำงานทางความคิดของนักคณิตศาสตร์เกี่ยวกับคำถามใช่หรือไม่ใช่ก็สามารถถูกแทนที่ด้วยเครื่องจักรได้อย่างสมบูรณ์ เพราะเพียงแค่เลือกจำนวนธรรมชาติnให้มีค่ามากพอที่เมื่อเครื่องจักรไม่ให้ผลลัพธ์ใดๆ ก็ไม่มีประโยชน์ที่จะคิดถึงปัญหาต่อไปอีก

ในทำนองเดียวกันStephen Cook (โดยถือว่าไม่เพียงแต่มีการพิสูจน์เท่านั้น แต่ยังรวมถึงอัลกอริทึมที่มีประสิทธิภาพในทางปฏิบัติด้วย) กล่าวว่า: ^{[ 29 ]}

...  มันจะพลิกโฉมวงการคณิตศาสตร์โดยอนุญาตให้คอมพิวเตอร์ค้นหาบทพิสูจน์เชิงรูปธรรมของทฤษฎีบทใดๆ ที่มีบทพิสูจน์ความยาวที่เหมาะสมได้ เนื่องจากบทพิสูจน์เชิงรูปธรรมสามารถจดจำได้ง่ายในเวลาพหุนาม ตัวอย่างปัญหาอาจรวมถึงปัญหาที่ได้รับรางวัล CMI ทั้งหมด ด้วย

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

Donald Knuthได้กล่าวว่าเขาเชื่อว่า P  =  NP แต่ยังคงสงวนท่าทีเกี่ยวกับผลกระทบของการพิสูจน์ที่เป็นไปได้: ^{[ 39 ]}

[...] ถ้าคุณลองนึกภาพจำนวนMที่เป็นจำนวนจำกัดแต่มีขนาดใหญ่มาก—เช่น จำนวน 10↑↑↑↑3 ที่กล่าวถึงในบทความของผมเรื่อง "การรับมือกับความจำกัด"—แล้วจะมีอัลกอริทึมที่เป็นไปได้จำนวนมหาศาลที่ทำการดำเนินการบิตไวส์ การบวก หรือการเลื่อนบิตจำนวนn ^M ครั้งบนบิตที่กำหนดจำนวน nบิต และเป็นเรื่องยากที่จะเชื่อว่าอัลกอริทึมเหล่านั้นทั้งหมดจะล้มเหลว อย่างไรก็ตาม ประเด็นหลักของผมคือ ผมไม่เชื่อว่าความเท่าเทียมกัน P  =  NP จะมีประโยชน์แม้ว่าจะได้รับการพิสูจน์แล้วก็ตาม เพราะการพิสูจน์เช่นนั้นเกือบจะแน่นอนว่าจะไม่สามารถสร้างสรรค์ได้

แม้ว่าปัญหา P  =  NP ยังคงเป็นปริศนาอยู่ แม้จะมีรางวัลมูลค่าหลายล้านดอลลาร์และการวิจัยอย่างทุ่มเทมากมาย แต่ความพยายามในการแก้ปัญหานี้ได้นำไปสู่เทคนิคใหม่ๆ หลายอย่าง โดยเฉพาะอย่างยิ่ง การวิจัยที่ได้ผลดีที่สุดเกี่ยวกับปัญหา P  =  NP คือการแสดงให้เห็นว่าเทคนิคการพิสูจน์ที่มีอยู่ไม่เพียงพอที่จะตอบคำถามนี้ ซึ่งชี้ให้เห็นว่าจำเป็นต้องมีแนวทางทางเทคนิคใหม่ๆ

เพื่อเป็นหลักฐานเพิ่มเติมถึงความยากของปัญหา เทคนิคการพิสูจน์ที่รู้จักเกือบทั้งหมดในทฤษฎีความซับซ้อนของการคำนวณนั้นล้วนตกอยู่ในการจัดประเภทใดประเภทหนึ่งต่อไปนี้ ซึ่งทั้งหมดไม่เพียงพอที่จะพิสูจน์ว่า P  ≠  NP:

อุปสรรคเหล่านี้เป็นอีกเหตุผลหนึ่งที่ทำให้ปัญหา NP-complete มีประโยชน์: หากสามารถแสดงให้เห็นอัลกอริทึมที่ใช้เวลาในการประมวลผลแบบพหุนามสำหรับปัญหา NP-complete ได้ นั่นจะเป็นการแก้ปัญหา P  =  NP ในลักษณะที่ไม่ถูกตัดออกโดยผลลัพธ์ข้างต้น

อุปสรรคเหล่านี้ทำให้ผู้เชี่ยวชาญด้านคอมพิวเตอร์บางคนเสนอว่าปัญหา P เทียบกับ NP อาจเป็นอิสระจากระบบสัจพจน์มาตรฐาน เช่นZFC (ไม่สามารถพิสูจน์หรือหักล้างได้ภายในระบบเหล่านั้น) ผลลัพธ์ที่เป็นอิสระอาจหมายความว่า P  ≠  NP และไม่สามารถพิสูจน์ได้ใน (เช่น) ZFC หรือว่า P  =  NP แต่ไม่สามารถพิสูจน์ได้ใน ZFC ว่าอัลกอริทึมเวลาพหุนามใด ๆ นั้นถูกต้อง^{[ 46 ]}อย่างไรก็ตาม หากปัญหาไม่สามารถตัดสินได้แม้จะมีสมมติฐานที่อ่อนกว่ามากซึ่งขยายสัจพจน์ของ Peanoสำหรับเลขคณิตจำนวนเต็ม อัลกอริทึมเวลาพหุนามเกือบทั้งหมดก็มีอยู่สำหรับปัญหา NP ทั้งหมด^{[ 47 ]}ดังนั้น สมมติ (ดังที่นักทฤษฎีความซับซ้อนส่วนใหญ่ทำ) ว่าปัญหา NP บางปัญหาไม่มีอัลกอริทึมที่มีประสิทธิภาพ การพิสูจน์ความเป็นอิสระด้วยเทคนิคเหล่านั้นจึงเป็นไปไม่ได้ นอกจากนี้ยังหมายความว่าการพิสูจน์ความเป็นอิสระจาก PA หรือ ZFC ด้วยเทคนิคปัจจุบันนั้นไม่ง่ายไปกว่าการพิสูจน์ว่าปัญหา NP ทั้งหมดมีอัลกอริทึมที่มีประสิทธิภาพ

ปัญหา P  =  NP สามารถกล่าวใหม่ได้ว่าเป็นประโยคตรรกะบางประเภท ซึ่งเป็นผลมาจากการทำงานในด้าน ความซับซ้อน เชิงพรรณนา

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

ในทำนองเดียวกัน NP คือเซตของภาษาที่สามารถแสดงออกมาได้ในตรรกะลำดับที่สอง แบบมีอยู่จริง —นั่นคือ ตรรกะลำดับที่สองที่ถูกจำกัดไม่ให้มีการกำหนดปริมาณแบบสากลเหนือความสัมพันธ์ ฟังก์ชัน และเซตย่อย ภาษาในลำดับชั้นพหุนาม PH สอดคล้องกับตรรกะลำดับที่สองทั้งหมด ดังนั้น คำถามที่ว่า "P เป็นเซตย่อยที่แท้จริงของ NP หรือไม่" สามารถกำหนดใหม่ได้เป็น "ตรรกะลำดับที่สองแบบมีอยู่จริงสามารถอธิบายภาษา (ของโครงสร้างเรียงลำดับเชิงเส้นจำกัดที่มีลายเซ็นที่ไม่ธรรมดา) ที่ตรรกะลำดับแรกที่มีจุดตรึงน้อยที่สุดไม่สามารถทำได้หรือไม่" ^{[ 48 ]}คำว่า "มีอยู่จริง" สามารถละทิ้งได้จากการกำหนดลักษณะก่อนหน้านี้ เนื่องจาก P  = NP ก็ต่อเมื่อ P = PH  เท่านั้น(เนื่องจากข้อแรกจะพิสูจน์ว่า NP = co-NP ซึ่งในทางกลับกันหมายความว่า NP = PH)      

ไม่มีอัลกอริทึมใดที่รู้จักสำหรับปัญหา NP-complete ที่ทำงานในเวลาพหุนาม อย่างไรก็ตาม มีอัลกอริทึมที่รู้จักสำหรับปัญหา NP-complete ที่หาก P  =  NP อัลกอริทึมจะทำงานในเวลาพหุนามบนอินสแตนซ์ที่ยอมรับได้ (แม้ว่าจะมีค่าคงที่มหาศาล ทำให้ไม่สามารถใช้งานอัลกอริทึมได้จริง) อย่างไรก็ตาม อัลกอริทึมเหล่านี้ไม่จัดว่าเป็นเวลาพหุนาม เพราะเวลาในการทำงานบนอินสแตนซ์ที่ปฏิเสธนั้นไม่ใช่พหุนาม อัลกอริทึมต่อไปนี้ ซึ่งเป็นผลงานของLevin (โดยไม่มีการอ้างอิงใดๆ) เป็นตัวอย่างหนึ่ง อัลกอริทึมนี้ยอมรับภาษา NP-complete SUBSET-SUM ได้อย่างถูกต้อง และทำงานในเวลาพหุนามบนอินพุตที่อยู่ใน SUBSET-SUM ก็ต่อเมื่อ P  =  NP เท่านั้น:

// อัลกอริทึมที่ยอมรับภาษา SUBSET-SUM ซึ่งเป็นปัญหา NP-complete // // นี่คืออัลกอริทึมเวลาพหุนามก็ต่อเมื่อ P = NP เท่านั้น// // "เวลาพหุนาม" หมายความว่ามันจะคืนค่า "ใช่" ในเวลาพหุนามเมื่อ// คำตอบควรจะเป็น "ใช่" และจะทำงานไปเรื่อยๆ เมื่อคำตอบเป็น "ไม่ใช่" // // อินพุต: S = เซตของจำนวนเต็มจำกัด// เอาต์พุต: "ใช่" ถ้าเซตย่อยใดๆ ของ S รวมกันได้ 0 // ทำงานไปเรื่อยๆ โดยไม่มีเอาต์พุตอื่นๆ// หมายเหตุ: "หมายเลขโปรแกรม M" คือโปรแกรมที่ได้จาก// การเขียนจำนวนเต็ม M ในรูปแบบไบนารี จากนั้น// พิจารณาสตริงของบิตนั้นว่าเป็น// โปรแกรม ทุกโปรแกรมที่เป็นไปได้สามารถสร้างได้ // ด้วยวิธีนี้ แม้ว่าส่วนใหญ่จะไม่ได้ทำอะไรเลย// เนื่องจากข้อผิดพลาดทางไวยากรณ์ สำหรับ K = 1...∞ สำหรับ M = 1...K เรียกใช้โปรแกรมหมายเลข M เป็นจำนวน K ขั้นตอน โดยใช้ข้อมูลป้อนเข้า S ถ้าโปรแกรมแสดงผลออกมาเป็นรายการของจำนวนเต็มที่ไม่ซ้ำกัน และจำนวนเต็มทั้งหมดอยู่ใน S และผลรวมของจำนวนเต็มเท่ากับ 0 แล้ว แสดงผล "ใช่" และหยุด

นี่คืออัลกอริธึมที่ทำงานในเวลาพหุนาม โดยยอมรับภาษาที่เป็นปัญหา NP-complete ก็ต่อเมื่อ P  =  NP เท่านั้น "การยอมรับ" หมายความว่ามันให้คำตอบ "ใช่" ในเวลาพหุนาม แต่จะทำงานไปเรื่อยๆ ไม่มีที่สิ้นสุดเมื่อคำตอบคือ "ไม่" (เรียกอีกอย่างว่ากึ่งอัลกอริธึม )

อัลกอริทึมนี้ไม่สามารถนำไปใช้ได้จริงอย่างมาก แม้ว่า P  =  NP ก็ตาม หากโปรแกรมที่สั้นที่สุดที่สามารถแก้ปัญหา SUBSET-SUM ได้ในเวลาพหุนามมี ความยาว b บิต อั ^ลกอริทึมข้างต้นจะลองใช้โปรแกรมอื่นอย่างน้อย2b − 1โปรแกรมก่อน

แม้ว่าปัญหา P เทียบกับ NP โดยทั่วไปจะถือว่ายังไม่ได้รับการแก้ไข^{[ 50 ]}แต่นักวิจัยสมัครเล่นและนักวิจัยมืออาชีพบางคนได้อ้างว่ามีวิธีแก้ไขGerhard J. Woegingerได้รวบรวมรายการหลักฐานที่อ้างว่าถูกต้อง 116 รายการตั้งแต่ปี 1986 ถึง 2016 ซึ่ง 61 รายการเป็นหลักฐานของ P  =  NP, 49 รายการเป็นหลักฐานของ P  ≠  NP และ 6 รายการพิสูจน์ผลลัพธ์อื่นๆ เช่น ปัญหาไม่สามารถตัดสินได้^{[ 51 ]}ความพยายามบางอย่างในการแก้ปัญหา P เทียบกับ NP ได้รับความสนใจจากสื่อในช่วงสั้นๆ^{[ 52 ]}แม้ว่าความพยายามเหล่านี้จะถูกหักล้างไปแล้วก็ตาม

ภาพยนตร์เรื่องTravelling Salesmanกำกับโดย Timothy Lanzone เป็นเรื่องราวของนักคณิตศาสตร์สี่คนที่ได้รับการว่าจ้างจากรัฐบาลสหรัฐฯ ให้แก้ปัญหา P เทียบกับ NP ^{[ 53 ]}

ในตอนที่หกของซีซั่นที่เจ็ดของThe Simpsonsเรื่อง " Treehouse of Horror VI " สมการ P = NP ปรากฏให้เห็นไม่นานหลังจากที่โฮเมอร์บังเอิญเข้าไปใน "มิติที่สาม" ^{[ 54 ] [ 55 ]}  

ในตอนที่สองของซีซั่นที่ 2 ของElementaryเรื่อง"Solve for X"โฮล์มส์และวัตสันสืบสวนคดีฆาตกรรมนักคณิตศาสตร์ที่พยายามแก้ปัญหา P เทียบกับ NP ^{[ 56 ] [ 57 ]}

ในตอน " Put Your Head on My Shoulders " จากซีซั่นที่สองของซีรีส์แอนิเมชั่นFuturamaมีการอ้างอิงภาพถึงปัญหา P เทียบกับ NP ปรากฏอยู่ในฉากหลัง ในฉากที่ฟรายและเอมี่ หว่อง เพื่อนร่วมงานของเขาเข้าไปในห้องเก็บของเพื่อคุยกันเป็นการส่วนตัว บนชั้นวางด้านหลังพวกเขาข้างกล่องที่มีป้ายกำกับว่า "Emergency Beans" มีหนังสือสองเล่มที่มีขนาดเท่ากัน เล่มหนึ่งมีเครื่องหมาย "P" และอีกเล่มมีเครื่องหมาย "NP" ^{[ 58 ] [ 59 ]}

• ปัญหา RเทียบกับREโดยที่ R เป็นอนาล็อกของคลาส P และ RE เป็นอนาล็อกของคลาส NP คลาสเหล่านี้ไม่เท่ากัน เพราะปัญหาที่ไม่สามารถตัดสินได้แต่ตรวจสอบได้มีอยู่จริง ตัวอย่างเช่นปัญหาที่สิบของฮิลเบิร์ตซึ่งเป็น RE-complete ^{[ 60 ]}
• ปัญหาที่คล้ายกันนี้มีอยู่ในทฤษฎีความซับซ้อนของพีชคณิต : ปัญหา VP เทียบกับ VNPเช่นเดียวกับ P เทียบกับ NP คำตอบในปัจจุบันยังไม่เป็นที่ทราบ^{[ 61 ] [ 60 ]}
• FPTเทียบกับW[1]เป็นปัญหาที่คล้ายคลึงกันใน ความซับซ้อน ของพารามิเตอร์

• สมมติฐานเวลาแบบเลขชี้กำลัง
• รายชื่อปัญหาที่ยังแก้ไม่ตกในสาขาวิทยาการคอมพิวเตอร์
• รายชื่อปัญหาที่ยังแก้ไม่ตกในวิชาคณิตศาสตร์
• การคาดเดาเกมที่ไม่เหมือนใคร

• เรเชล โครเวลล์ (28 พฤษภาคม 2021) "คำถามที่ยังแก้ไม่ตกอันดับต้น ๆ ในคณิตศาสตร์ยังคงเป็นปริศนาอยู่ มีเพียงหนึ่งในเจ็ดปัญหา Millennium Prize Problems ที่ได้รับการตั้งชื่อเมื่อ 21 ปีก่อนเท่านั้นที่ได้รับการแก้ไขแล้ว" www.scientificamerican.comสืบค้นเมื่อ21 มิถุนายน 2021 ปัญหานี้เกี่ยวข้องกับประเด็นที่ว่า คำถามที่ตรวจสอบได้ง่าย (กลุ่มคำถามที่เรียกว่า NP) จะมีคำตอบที่หาได้ง่ายด้วยหรือ ไม่(กลุ่มคำถามที่เรียกว่า P)
• Hosch, William L (11 สิงหาคม 2552). "ปัญหาคณิตศาสตร์ P เทียบกับ NP" . สารานุกรมบริแทนนิกา . สืบค้นเมื่อ20 มิถุนายน 2564 .
• "ปัญหา NP" . www.claymath.org (Cook, Levin) . เก็บถาวรจากต้นฉบับเมื่อวันที่ 18 มิถุนายน 2021 . เรียกดูเมื่อวันที่ 20 มิถุนายน 2021 . สมมติว่าคุณกำลังจัดหาที่พักให้กับนักศึกษามหาวิทยาลัยจำนวนสี่ร้อยคน พื้นที่จำกัดและมีเพียงหนึ่งร้อยคนเท่านั้นที่จะได้รับที่พักในหอพัก เพื่อให้เรื่องยุ่งยากขึ้น คณบดีได้ให้รายชื่อคู่ของนักศึกษาที่ไม่เข้ากันมาให้คุณ และขอให้คุณอย่าเลือกคู่ใดจากรายชื่อนี้ในตัวเลือกสุดท้ายของคุณ นี่เป็นตัวอย่างของสิ่งที่นักวิทยาศาสตร์คอมพิวเตอร์เรียกว่าปัญหา NP...

• คอร์เมน, โทมัส (2001). บทนำสู่อัลกอริธึม . เคมบริดจ์, แมสซาชูเซตส์: สำนักพิมพ์ MIT . ISBN 978-0-262-03293-3.
• Garey, Michael R. ; Johnson, David S. (1979). คอมพิวเตอร์และความยากลำบากในการแก้ปัญหา: คู่มือทฤษฎีความสมบูรณ์ของ NPชุดหนังสือในสาขาวิทยาศาสตร์คณิตศาสตร์ (  ฉบับพิมพ์ครั้งที่ 1). นิวยอร์ก: WH Freeman and Company . ISBN 9780716710455. MR 0519066 . OCLC 247570676 .  
• Goldreich, Oded (2010). P, NP และความสมบูรณ์ของ NP . เคมบริดจ์ ประเทศอังกฤษ: สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ . ISBN 978-0-521-12254-2.ร่างออนไลน์
• Immerman, Neil (1987). "ภาษาที่สามารถจับคลาสความซับซ้อนได้" SIAM Journal on Computing . 16 (4): 760– 778. CiteSeerX 10.1.1.75.3035 . doi : 10.1137/0216051 . 
• Papadimitriou, Christos (1994). ความซับซ้อนของการคำนวณ . บอสตัน, แมสซาชูเซตส์: Addison-Wesley . ISBN 978-0-201-53082-7.

• ฟอร์ทนอว์, แอล.; กาซาร์ช, ดับเบิลยู. "ความซับซ้อนในการคำนวณ "
• วิทยานิพนธ์เรื่อง "ความยากลำบากในการประมาณค่าระหว่าง P และ NP"ของ Aviad Rubinsteinได้รับรางวัลวิทยานิพนธ์ระดับปริญญาเอกยอดเยี่ยมประจำปี 2017จากACM
• "P เทียบกับ NP และสวนสัตว์แห่งความซับซ้อนในการคำนวณ" 26 สิงหาคม 2014 เก็บถาวรจากต้นฉบับเมื่อ 24 พฤศจิกายน 2021 –ผ่านทางYouTube