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

• ปัญหา P เทียบกับ NP – ปัญหา P เทียบกับ NP เป็นคำถามสำคัญที่ยังแก้ไม่ตกในวิทยาศาสตร์คอมพิวเตอร์ ซึ่งถามว่าปัญหาทุกปัญหาที่สามารถตรวจสอบคำตอบได้อย่างรวดเร็วด้วยคอมพิวเตอร์ (NP) สามารถแก้ไขได้อย่างรวดเร็วด้วยคอมพิวเตอร์ (P) หรือไม่ คำถามนี้มีนัยสำคัญอย่างยิ่งต่อสาขาต่างๆ เช่น การเข้ารหัสลับ การออกแบบอัลกอริทึม และทฤษฎีการคำนวณ^{[ 1 ]}
• BQPและNPมีความสัมพันธ์กันอย่างไร?
• ปัญหา NC = P
• ปัญหา NP = co-NP
• P = ปัญหา BPP
• P = ปัญหา PSPACE
• ปัญหา L = NL
• ปัญหา PH = PSPACE
• ปัญหา L = P
• ปัญหาL = RL
• การคาดเดาเกมที่ไม่เหมือนใคร
• สมมติฐานเรื่องเวลาแบบเลขชี้กำลังนั้นถูกต้องหรือไม่?
  • สมมติฐานเวลาแบบเลขชี้กำลังที่แข็งแกร่ง (SETH) เป็นจริงหรือไม่?
• ฟังก์ชันทางเดียว มีอยู่จริง หรือไม่?
  • การเข้ารหัสแบบกุญแจสาธารณะเป็นไปได้หรือไม่?
• สมมติฐานลอการิทึมแรงค์
• สมมติฐานของฮาร์ทมานิส-สเติร์นส์

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

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

• การทำให้กราฟเป็นมาตรฐานโดยใช้เวลาเชิงพหุนามเทียบเท่ากับปัญหาความเหมือนกันของกราฟหรือไม่?
• สามารถระบุค่ากำลังของใบไม้และ ค่ากำลัง k ของใบไม้ได้ภายในเวลาพหุนามหรือไม่?
• เกมพาริตีสามารถแก้ได้ภายในเวลาพหุนามหรือไม่?
• สามารถคำนวณระยะการหมุนระหว่างต้นไม้ไบนารี สองต้นได้ในเวลาพหุนามหรือไม่?
• กราฟที่มีความกว้างคลิก จำกัดสามารถ รับรู้ได้ในเวลาพหุนามหรือไม่? ^{[ 3 ]}
• สามารถหาเส้นกึ่งจีโอดีสปิดที่เรียบง่ายบนทรงหลายเหลี่ยมนูนได้ในเวลาพหุนามหรือไม่? ^{[ 4 ]}
• สามารถ ค้นหา การฝังพร้อมกันด้วยขอบคงที่สำหรับกราฟสองกราฟที่กำหนดได้ในเวลาพหุนามหรือไม่? ^{[ 5 ]}
• ในแบบจำลองเครื่องจักรทัวริงสามารถ แก้ ปัญหาผลรวมรากที่สอง ได้ในเวลาพหุนามหรือไม่?

• ปัญหาของสโกเลม : สามารถตัดสินได้หรือไม่ว่าลำดับเวียนเกิดเชิงเส้นพีชคณิตมีศูนย์หรือไม่?
• ปัญหาข้อที่สิบของฮิลเบิร์ตเกี่ยวกับขอบเขตของจำนวนตรรกยะ

• ข้อสันนิษฐานเรื่องความเหมาะสมเชิงพลวัต : ต้นไม้แบบสไปลย์มีอัตราส่วนการแข่งขันที่จำกัดหรือไม่?
• สามารถสร้างโครงสร้างต้นไม้ค้นหาเชิงลึก (depth-first search tree) ใน ภาษา NC ได้ หรือไม่?
• สามารถคำนวณการแปลงฟูริเยร์แบบเร็วได้ ใน เวลาo ( n log n ) หรือไม่?
• อัลกอริทึม ใดเร็วที่สุดสำหรับการคูณ จำนวน สอง จำนวนที่มี nหลัก?
• ความซับซ้อนของเวลาเฉลี่ยต่ำสุดที่เป็นไปได้ของShellsortเมื่อใช้ลำดับช่องว่างคงที่แบบกำหนดได้ คือเท่าใด
• สามารถ แก้ 3SUMได้ในเวลาที่น้อยกว่ากำลังสองอย่างมากหรือไม่ กล่าวคือ ในเวลาO ( n ^2−ϵ )สำหรับϵ > 0 บางค่า ?
• ระยะห่างการแก้ไขระหว่างสตริงสองสตริงที่มีความยาวnสามารถคำนวณได้ในเวลาที่น้อยกว่ากำลังสองอย่างมากหรือไม่? (สิ่งนี้เป็นไปได้ก็ต่อเมื่อสมมติฐานเวลาเลขชี้กำลัง อย่างมาก เป็นเท็จเท่านั้น)
• การเรียงลำดับ X + Yสามารถทำได้ในเวลาo ( n ² log n ) หรือไม่?
• อัลกอริทึม ใดเร็วที่สุดสำหรับการคูณเมทริกซ์ ?
• เส้นทางที่สั้นที่สุดระหว่างทุกคู่จุดสามารถคำนวณได้ในเวลาที่ต่ำกว่ากำลังสามอย่างมากหรือไม่ กล่าวคือ ในเวลาO ( V ^3−ϵ )สำหรับϵ > 0 บางค่า ?
• ทฤษฎีบท Schwartz–Zippelสำหรับการทดสอบเอกลักษณ์พหุนามสามารถลดความสุ่มลงได้ หรือ ไม่?
• การเขียนโปรแกรมเชิงเส้นมี อัลกอริทึมที่ทำงาน ในเวลาพหุนามอย่างเข้มข้นหรือไม่? (นี่คือปัญหาข้อที่ 9 ในรายการปัญหาของ Smale )
• ต้องถามคำถามกี่ครั้งจึงจะตัดเค้กได้โดยไม่รู้สึกอิจฉา ?
• ความซับซ้อนเชิงอัลกอริทึมของปัญหาต้นไม้แผ่คลุมขั้นต่ำ คืออะไร? หรือกล่าวอีกนัยหนึ่ง ความซับซ้อน ของต้นไม้ตัดสินใจของปัญหาต้นไม้แผ่คลุม ขั้นต่ำ คืออะไร ? อัลกอริทึมที่ดีที่สุดในการคำนวณต้นไม้แผ่คลุมขั้นต่ำเป็น ที่ทราบกันดีแต่เนื่องจากต้องอาศัยต้นไม้ตัดสินใจ ความซับซ้อนของมันจึงยังไม่เป็นที่ทราบ
• ข้อสันนิษฐานของกิลเบิร์ต-พอลแล็ก : อัตราส่วนสไตเนอร์ของระนาบยุคลิดเท่ากับเท่าใด?${\displaystyle 2/{\sqrt {3}}}$

• ข้อสันนิษฐานของ Barendregt–Geuvers–Klop : ระบบประเภทบริสุทธิ์แบบอ่อนทุกระบบจะเป็นแบบแข็งด้วยหรือไม่?

• ตรรกะเชิงเส้นแบบคูณและเลขชี้กำลัง สามารถตัดสินได้ หรือไม่?
• สมมติฐาน ของAanderaa–Karp–Rosenbergเป็นจริงหรือไม่?
• ข้อสันนิษฐานของเชอร์นี : ถ้าออโตมาตาจำกัดเชิงกำหนดที่มีสถานะต่างๆ มีคำประสานจะต้องมีคำประสานที่มีความยาวไม่เกินหรือไม่?${\displaystyle n}$${\displaystyle (n-1)^{2}}$
• ปัญหาความสูงของดาวแบบทั่วไป : ภาษาปกติทั้งหมดสามารถแสดงได้โดยใช้การแสดงออกปกติแบบทั่วไปที่มีความลึกของการซ้อนกันที่จำกัดของดาวคลีนได้หรือไม่?
• ปัญหาการแยกคำ : ต้องใช้สถานะกี่สถานะในออโตมาตาจำกัดเชิงกำหนด ที่แสดงพฤติกรรมแตกต่างกันบน สตริงสอง สตริง ที่มีความยาวเท่า กัน ?${\displaystyle n}$
• สถานะ ความสมบูรณ์แบบของทัวริง (Turing completeness)ของระบบอัตโนมัติเซลลูลาร์พื้นฐาน ที่ไม่ซ้ำกันทั้งหมด คืออะไร?
• จงพิจารณาว่าความยาวของคำที่ไม่สามารถเติมเต็มได้ขั้นต่ำของเป็นพหุนามในหรือไม่ หรือแม้แต่ใน เป็นที่ทราบกันว่าเป็นรหัสที่มีความยาวแปรผันได้ถ้า สำหรับทุกหมายความว่าและสำหรับทุกในกรณีเช่นนี้ เรายังไม่ทราบว่ามีขอบเขตพหุนามอยู่หรือไม่ นี่อาจเป็นการลดทอนสมมติฐานของ Restivo (ซึ่งถูกพิสูจน์ว่าผิดไปแล้วโดยทั่วไป แม้ว่าขอบเขตบนยังคงไม่เป็นที่ทราบ)${\displaystyle M}$${\displaystyle l(M)}$${\displaystyle sl(M)}$${\displaystyle M}$${\displaystyle u_{1},...,u_{n},v_{1},...,v_{m}\in M}$${\displaystyle u_{1}...u_{n}=v_{1}...v_{m}}$${\displaystyle n=m}$${\displaystyle u_{i}=v_{i}}$${\displaystyle 0<i\leq n}$
• จงหาจำนวนเต็มบวกทั้งหมดที่เมื่อนำมาต่อกันแล้วจะ ได้ จำนวนอักขระที่แตกต่างกันไม่เกิน จำนวนหนึ่ง โดยที่ และ มีค่าคง ที่${\displaystyle n}$${\displaystyle n}$${\displaystyle n^{2}}$${\displaystyle b}$${\displaystyle k}$${\displaystyle b}$${\displaystyle k}$

• รายชื่อปัญหาที่ยังแก้ไม่ตกในวิชาฟิสิกส์
• รายชื่อปัญหาที่ยังแก้ไม่ตกในวิชาคณิตศาสตร์

• Woeginger, Gerhard J. "ปัญหาที่ยังเปิดอยู่เกี่ยวกับอัลกอริทึมที่แม่นยำ" . คณิตศาสตร์ประยุกต์แบบไม่ต่อเนื่อง . 156 (2008): 397– 405.
• รายการปัญหาที่ยังไม่ได้รับการแก้ไขของ RTA – ปัญหาที่ยังไม่ได้รับการแก้ไขในการเขียนโค้ดใหม่
• รายชื่อปัญหาที่ยังไม่ได้รับการแก้ไขของ TLCA – ปัญหาที่ยังไม่ได้รับการแก้ไขในสาขาแคลคูลัสแลมบ์ดาแบบมีชนิดข้อมูล