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

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

ข้อสมมติเกี่ยวกับความยากในการคำนวณยังมีประโยชน์ในการชี้นำ นักออกแบบ อัลกอริทึมด้วยกล่าวคือ อัลกอริทึมที่เรียบง่ายไม่น่าจะหักล้างข้อสมมติเกี่ยวกับความยากในการคำนวณที่ได้รับการศึกษามาเป็นอย่างดี เช่นP ≠ NP

นักวิทยาศาสตร์คอมพิวเตอร์มีวิธีการประเมินที่แตกต่างกันว่าสมมติฐานเรื่องความยากแบบใดน่าเชื่อถือมากกว่ากัน

เรากล่าวว่าสมมติฐานหนึ่งแข็งแกร่งกว่าสมมติฐานอีกสมมติฐานหนึ่งเมื่อสมมติฐาน อีกสมมติฐานหนึ่งบ่ง ชี้ว่า (และในทางกลับกันเป็นเท็จหรือไม่ทราบ) กล่าวอีกนัยหนึ่ง แม้ว่าสมมติฐานหนึ่ง จะเป็น เท็จ สมมติฐานอีกสมมติฐานหนึ่งก็อาจยังคงเป็นจริง และโปรโตคอลการเข้ารหัสที่อิงตามสมมติฐานหนึ่งก็อาจยังคงปลอดภัยที่จะใช้งานได้ ดังนั้นเมื่อออกแบบโปรโตคอลการเข้ารหัส เราจึงหวังว่าจะสามารถพิสูจน์ความปลอดภัยได้โดยใช้สมมติฐาน ที่อ่อนแอที่สุด เท่าที่จะเป็นไปได้${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$

สมมติฐานกรณีเฉลี่ยกล่าวว่าปัญหาเฉพาะนั้นยากในกรณีส่วนใหญ่จากการกระจายตัวที่ชัดเจน ในขณะที่ สมมติฐาน กรณีเลวร้ายที่สุดกล่าวว่าปัญหานั้นยากในบางกรณีเท่านั้น สำหรับปัญหาที่กำหนด ความยากในกรณีเฉลี่ยบ่งบอกถึงความยากในกรณีเลวร้ายที่สุด ดังนั้นสมมติฐานความยากในกรณีเฉลี่ยจึงแข็งแกร่งกว่าสมมติฐานความยากในกรณีเลวร้ายที่สุดสำหรับปัญหาเดียวกัน ยิ่งไปกว่านั้น แม้แต่สำหรับปัญหาที่ไม่สามารถเปรียบเทียบกันได้ สมมติฐานเช่นสมมติฐานเวลาเลขชี้กำลังมักถูกพิจารณาว่าดีกว่าสมมติฐานกรณีเฉลี่ยเช่น สมมติฐาน การวางกลุ่ม^{[ 1 ]}อย่างไรก็ตาม สำหรับแอปพลิเคชันการเข้ารหัส การรู้ว่าปัญหามีกรณีที่ยากบางกรณี (ปัญหานั้นยากในกรณีเลวร้ายที่สุด) นั้นไร้ประโยชน์เพราะไม่ได้ให้วิธีการสร้างกรณีที่ยากแก่เรา^{[ 2 ]}โชคดีที่สมมติฐานกรณีเฉลี่ยจำนวนมากที่ใช้ในการเข้ารหัส (รวมถึงRSA , ลอการิทึมแบบไม่ต่อเนื่องและปัญหาแลตทิซ บางอย่าง ) สามารถอิงตามสมมติฐานกรณีเลวร้ายที่สุดผ่านการลดกรณีเลวร้ายที่สุดเป็นกรณีเฉลี่ยได้^{[ 3 ]}

ลักษณะที่พึงประสงค์ของสมมติฐานความยากในการคำนวณคือความสามารถในการพิสูจน์ความเท็จกล่าวคือ หากสมมติฐานนั้นเป็นเท็จ ก็จะสามารถพิสูจน์ได้ โดยเฉพาะอย่างยิ่งNaor (2003)ได้นำเสนอแนวคิดอย่างเป็นทางการของความสามารถในการพิสูจน์ความเท็จทางด้านการเข้ารหัส^{[ 4 ]}โดยคร่าวๆ สมมติฐานความยากในการคำนวณจะกล่าวได้ว่าสามารถพิสูจน์ความเท็จได้ หากสามารถกำหนดเป็นสูตรในรูปของความท้าทาย: โปรโตคอลแบบโต้ตอบระหว่างฝ่ายตรงข้ามและผู้ตรวจสอบที่มีประสิทธิภาพ โดยที่ฝ่ายตรงข้ามที่มีประสิทธิภาพสามารถโน้มน้าวให้ผู้ตรวจสอบยอมรับได้ก็ต่อเมื่อสมมติฐานนั้นเป็นเท็จ เท่านั้น

มีข้อสมมติฐานเกี่ยวกับความยากในการเข้ารหัสอยู่หลายแบบ นี่คือรายชื่อข้อสมมติฐานที่ใช้กันทั่วไปบางส่วน และโปรโตคอลการเข้ารหัสบางส่วนที่ใช้ข้อสมมติฐานเหล่านั้น

เมื่อกำหนดจำนวนเต็มประกอบ โดยเฉพาะอย่างยิ่งจำนวนเต็มที่เป็นผลคูณของจำนวนเฉพาะขนาด ใหญ่สอง จำนวน ปัญหาการแยกตัวประกอบจำนวนเต็มคือการหาและ(โดยทั่วไปแล้วคือการหาจำนวนเฉพาะที่ทำให้) การหาอัลกอริทึมสำหรับการแยกตัวประกอบจำนวนเต็มที่ทำงานได้ในเวลาที่เป็นพหุนามตามขนาดของการแสดงผล ( ) ยังคงเป็น ปัญหาเปิด ที่สำคัญ ความปลอดภัยของโปรโตคอลการเข้ารหัสจำนวนมากอาศัยสมมติฐานที่ว่าการแยกตัวประกอบจำนวนเต็มเป็นเรื่องยาก (กล่าวคือไม่สามารถแก้ไขได้ในเวลาที่เป็นพหุนาม) ระบบการเข้ารหัสที่มีความปลอดภัยเทียบเท่ากับสมมติฐานนี้ ได้แก่ลายเซ็น Rabinและระบบการเข้ารหัส Okamoto–Uchiyama ระบบการเข้ารหัสอีกมากมายอาศัยสมมติฐานที่แข็งแกร่งกว่า เช่นRSAปัญหาเศษเหลือและการซ่อนค่า phi ${\displaystyle n}$${\displaystyle n=p\cdot q}$${\displaystyle p}$${\displaystyle q}$${\displaystyle p_{1},\dots ,p_{k}}$${\displaystyle n=\prod _{i}p_{i}}$${\displaystyle \log n}$

เมื่อกำหนดจำนวนประกอบเลขชี้กำลังและจำนวนหนึ่งปัญหาของ RSA คือการหาค่าปัญหานี้คาดการณ์ว่ายาก แต่จะง่ายขึ้นเมื่อทราบการแยกตัวประกอบของในระบบการเข้ารหัส RSAคือกุญแจสาธารณะคือการเข้ารหัสข้อความและการแยกตัวประกอบของคือกุญแจลับที่ใช้ในการถอดรหัส ${\displaystyle n}$${\displaystyle e}$${\displaystyle c:=m^{e}(\mathrm {mod} \;n)}$${\displaystyle m}$${\displaystyle n}$${\displaystyle (n,e)}$${\displaystyle c}$${\displaystyle m}$${\displaystyle n}$

กำหนดให้จำนวนประกอบและจำนวนเต็มปัญหาของเศษเหลือคือการพิจารณาว่ามีอยู่หรือไม่ (หรืออีกนัยหนึ่งคือ หาจำนวนประกอบ) ที่ทำให้ ${\displaystyle n}$${\displaystyle y,d}$${\displaystyle x}$

${\displaystyle x^{d}\equiv y{\pmod {n}}.}$

กรณีพิเศษที่สำคัญ ได้แก่ปัญหาเศษเหลือกำลังสองและปัญหาเศษเหลือประกอบเชิงตัดสินใจเช่นเดียวกับกรณีของ RSA ปัญหานี้ (และกรณีพิเศษต่างๆ) คาดการณ์กันว่ายาก แต่จะง่ายขึ้นเมื่อพิจารณาการแยกตัวประกอบของ ระบบการเข้ารหัสบางระบบที่อาศัยความยากของปัญหาเศษเหลือ ได้แก่: ${\displaystyle n}$

• ระบบการเข้ารหัส Goldwasser–Micali (ปัญหาเศษเหลือกำลังสอง)
• เครื่องกำเนิด Blum Blum Shub (ปัญหาเศษเหลือกำลังสอง)
• ระบบการเข้ารหัส Paillier (ปัญหาเศษเหลือเชิงประกอบการตัดสินใจ)
• ระบบการเข้ารหัสเบนาโลห์ (ปัญหาเศษเหลือสูง)
• ระบบการเข้ารหัส Naccache–Stern (ปัญหาความตกค้างสูง)

สำหรับจำนวนประกอบไม่ทราบวิธีการคำนวณฟังก์ชันโทเทียนต์ของออยเลอร์ อย่างมีประสิทธิภาพ สมมติฐานการซ่อนค่าฟีตั้งสมมติฐานว่าการคำนวณนั้นยากและยิ่งไปกว่านั้น การคำนวณตัวประกอบเฉพาะ ใด ๆ ของ ก็ยากเช่นกัน สมมติฐานนี้ใช้ในโปรโตคอลPIR ของ Cachin–Micali–Stadler ^{[ 5 ]}${\displaystyle m}$${\displaystyle \phi (m)}$${\displaystyle \phi (m)}$${\displaystyle \phi (m)}$

เมื่อกำหนดองค์ประกอบและจากกลุ่ม หนึ่ง ปัญหาลอการิทึมแบบไม่ต่อเนื่องจะถามหาจำนวนเต็ม ที่ ทำให้ ปัญหาลอการิทึมแบบไม่ต่อ เนื่องนั้นไม่สามารถเปรียบเทียบได้กับการแยกตัวประกอบจำนวนเต็ม แต่ความซับซ้อนในการคำนวณของทั้งสองปัญหานั้นใกล้เคียงกัน ${\displaystyle a}$${\displaystyle b}$${\displaystyle G}$${\displaystyle k}$${\displaystyle a=b^{k}}$

โปรโตคอลการเข้ารหัสส่วนใหญ่ที่เกี่ยวข้องกับปัญหาลอการิทึมแบบไม่ต่อเนื่องนั้น อาศัยสมมติฐาน Diffie–Hellman ที่แข็งแกร่งกว่า กล่าวคือ เมื่อกำหนดองค์ประกอบกลุ่มโดยที่เป็นตัวสร้างและเป็นจำนวนเต็มสุ่ม การหาค่า จะทำได้ยาก ตัวอย่างของโปรโตคอลที่ใช้สมมติฐานนี้ ได้แก่ การแลกเปลี่ยนกุญแจ Diffie–Hellmanดั้งเดิมรวมถึงการเข้ารหัส ElGamal (ซึ่งอาศัยDiffie–Hellmanแบบตัดสินใจ (DDH) ที่แข็งแกร่งกว่า) ${\displaystyle g,g^{a},g^{b}}$${\displaystyle g}$${\displaystyle a,b}$${\displaystyle g^{a\cdot b}}$

แผนที่เชิงเส้นหลายตัว (multilinear map ) คือฟังก์ชัน(โดยที่เป็นกลุ่ม ) ซึ่งสำหรับและ ใด ๆ ${\displaystyle e:G_{1},\dots ,G_{n}\rightarrow G_{T}}$${\displaystyle G_{1},\dots ,G_{n},G_{T}}$${\displaystyle g_{1},\dots ,g_{n}\in G_{1},\dots G_{n}}$${\displaystyle a_{1},\dots ,a_{n}}$

${\displaystyle e(g_{1}^{a_{1}},\dots ,g_{n}^{a_{n}})=e(g_{1},\dots ,g_{n})^{a_{1}\cdots a_{n}}}$.

สำหรับแอปพลิเคชันการเข้ารหัสลับ เราต้องการสร้างกลุ่มและแผนที่เพื่อให้แผนที่และการดำเนินการกลุ่มบนสามารถคำนวณได้อย่างมีประสิทธิภาพ แต่ปัญหาลอการิทึมแบบไม่ต่อเนื่องบนยังคงยาก^{[ 6 ]} แอปพลิเคชันบางอย่างต้องการสมมติฐานที่เข้มงวดกว่า เช่น อนาล็อกเชิงเส้นหลายตัวของสมมติฐาน Diffie-Hellman ${\displaystyle G_{1},\dots ,G_{n},G_{T}}$${\displaystyle e}$${\displaystyle G_{1},\dots ,G_{n},G_{T}}$${\displaystyle G_{1},\dots ,G_{n}}$

สำหรับกรณีพิเศษของแผนที่เชิงเส้นคู่ที่มีความปลอดภัยที่น่าเชื่อถือได้รับการสร้างขึ้นโดยใช้การจับคู่ Weilและการจับคู่ Tate ^{[ 7 ]} สำหรับโครงสร้างจำนวนมากได้รับการเสนอในช่วงไม่กี่ปีที่ผ่านมา แต่โครงสร้างเหล่านั้นจำนวนมากก็ถูกทำลาย และในปัจจุบันยังไม่มีฉันทามติเกี่ยวกับตัวเลือกที่ปลอดภัย^{[ 8 ]}${\displaystyle n=2}$${\displaystyle n>2}$

ระบบการเข้ารหัสบางระบบที่อาศัยสมมติฐานความยากแบบหลายเชิงเส้น ได้แก่:

• แผนผังโบเนห์-แฟรงคลิน (ดิฟฟี-เฮลแมนแบบทวิเชิงเส้น)
• Boneh–Lynn–Shacham (bilinear Diffie-Hellman)
• ผู้สมัคร Garg-Gentry-Halevi-Raykova-Sahai-Waters สำหรับการปกปิดความไม่สามารถแยกแยะได้และการเข้ารหัสฟังก์ชัน (จิ๊กซอว์หลายเส้น) ^{[ 9 ]}

ปัญหาการคำนวณพื้นฐานที่สุดบนแลตทิซคือปัญหาเวกเตอร์ที่สั้นที่สุด (SVP) : เมื่อกำหนดแลตทิซให้หาเวกเตอร์ที่ไม่เป็นศูนย์ที่สั้นที่สุดระบบการเข้ารหัสส่วนใหญ่ต้องการสมมติฐานที่เข้มงวดกว่าในรูปแบบต่างๆ ของ SVP เช่น ปัญหา ^เวกเตอร์อิสระที่สั้นที่สุด (SIVP) GapSVP [ ^{10 ]}หรือ Unique-SVP ^{[ 11 ]}${\displaystyle L}$${\displaystyle v\in L}$

ข้อสมมติฐานเรื่องความยากของแลตทิซที่มีประโยชน์ที่สุดในการเข้ารหัสลับคือสำหรับ ปัญหา การเรียนรู้ที่มีข้อผิดพลาด (LWE): เมื่อกำหนดตัวอย่างให้กับ โดยที่สำหรับฟังก์ชันเชิงเส้นบางฟังก์ชัน การเรียนรู้ โดยใช้พีชคณิตเชิงเส้นนั้นง่ายในปัญหา LWE อินพุตของอัลกอริทึมมีข้อผิดพลาด กล่าวคือ สำหรับแต่ละคู่ ด้วย ความน่าจะเป็นเล็กน้อยข้อผิดพลาดเหล่านี้เชื่อว่าทำให้ปัญหานี้ไม่สามารถแก้ไขได้ (สำหรับพารามิเตอร์ที่เหมาะสม) โดยเฉพาะอย่างยิ่ง มีการลดกรณีที่เลวร้ายที่สุดเป็นกรณีเฉลี่ยที่ทราบจากตัวแปรของ SVP ^{[ 12 ]}${\displaystyle (x,y)}$${\displaystyle y=f(x)}$${\displaystyle f(\cdot )}$${\displaystyle f(\cdot )}$${\displaystyle y\neq f(x)}$

สำหรับคอมพิวเตอร์ควอนตัมปัญหาการแยกตัวประกอบและลอการิทึมแบบไม่ต่อเนื่องนั้นง่าย แต่ปัญหาแลตทิซนั้นคาดว่าจะยาก^{[ 13 ]}ซึ่งทำให้ระบบการเข้ารหัสแบบแลตทิซ บางระบบ เป็นตัวเลือกสำหรับการเข้ารหัสหลังควอนตัม

ระบบการเข้ารหัสบางระบบที่อาศัยความยากของปัญหาแลตทิซ ได้แก่:

• NTRU (ทั้งNTRUEncryptและNTRUSign )
• ผู้สมัครส่วนใหญ่สำหรับการเข้ารหัสแบบโฮโมมอร์ฟิกอย่างสมบูรณ์

นอกจากการประยุกต์ใช้ในการเข้ารหัสแล้ว สมมติฐานเรื่องความยากลำบากยังถูกนำมาใช้ในทฤษฎีความซับซ้อนของการคำนวณเพื่อเป็นหลักฐานสำหรับข้อความทางคณิตศาสตร์ที่ยากต่อการพิสูจน์โดยไม่มีเงื่อนไข ในการประยุกต์ใช้เหล่านี้ เราจะพิสูจน์ว่าสมมติฐานเรื่องความยากลำบากนั้นบ่งบอกถึงข้อความเชิงทฤษฎีความซับซ้อนที่ต้องการ แทนที่จะพิสูจน์ว่าข้อความนั้นเป็นจริง สมมติฐานที่รู้จักกันดีที่สุดในประเภทนี้คือสมมติฐานที่ว่าP ≠ NP [ ^{14 ]}แต่ยังมีสมมติฐานอื่นๆ อีก เช่นสมมติฐานเวลาเลขชี้กำลัง [ ^{15 ] สมมติฐาน เกี่ยว กับ}กลุ่มที่ปลูกไว้และ สมมติฐาน เกี่ยวกับเกมที่ไม่ซ้ำกัน^{[ 16 ]}

ปัญหาการคำนวณที่ เลวร้ายที่สุดหลายปัญหานั้นเป็นที่ทราบกันดีว่ายากหรือแม้กระทั่งเป็นปัญหาสมบูรณ์สำหรับคลาสความซับซ้อน บางคลาส โดยเฉพาะอย่างยิ่งNP-hard (แต่บ่อยครั้งก็เป็นPSPACE-hard , PPAD-hardฯลฯ ด้วย) ซึ่งหมายความว่าปัญหาเหล่านั้นมีความยากอย่างน้อยก็เท่ากับปัญหาใดๆ ในคลาสเดียวกันหากปัญหาใดเป็นNP-hard (เมื่อเทียบกับการลดรูปในเวลาพหุนาม) ปัญหานั้นจะไม่สามารถแก้ไขได้ด้วยอัลกอริทึมในเวลาพหุนาม เว้นแต่ว่าสมมติฐานเรื่องความยากในการคำนวณจะเป็นเท็จ ${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$${\displaystyle P\neq C}$

สมมติฐานเวลาเลขชี้กำลัง (ETH) เป็นการเสริมความแข็งแกร่งของสมมติฐานความยากลำบาก ซึ่งตั้งข้อสันนิษฐานว่าปัญหาความพึงพอใจของบูลีน (SAT) ไม่เพียงแต่ไม่มีอัลกอริทึมเวลาพหุนามเท่านั้น แต่ยังต้องการเวลาเลขชี้กำลังอีกด้วย ( ) ^{[ 17 ]}สมมติฐานที่แข็งแกร่งกว่านั้น ซึ่งรู้จักกันในชื่อสมมติฐานเวลาเลขชี้กำลังที่แข็งแกร่ง (SETH) ตั้งข้อสันนิษฐานว่า-SATต้องการเวลา โดยที่ETH, SETH และสมมติฐานความยากลำบากในการคำนวณที่เกี่ยวข้อง ช่วยให้สามารถอนุมานผลลัพธ์ความซับซ้อนที่ละเอียดได้ เช่น ผลลัพธ์ที่แยกแยะเวลาพหุนามและเวลากึ่งพหุนาม [ ^{1 ]}หรือแม้กระทั่งเทียบกับ^{[ 18 ]}สมมติฐานดังกล่าวมีประโยชน์ใน ความ ^{ซับซ้อน}แบบพารามิเตอร์ด้วย^{[ 19 ]}${\displaystyle P\neq NP}$${\displaystyle 2^{\โอเมก้า (n)}}$${\displaystyle k}$${\displaystyle 2^{(1-\varepsilon _{k})n}}$${\displaystyle \lim _{k\rightarrow \infty }\varepsilon _{k}=0}$${\displaystyle n^{1.99}}$${\displaystyle n^{2}}$

ปัญหาการคำนวณบางอย่างถือว่ายากโดยเฉลี่ยบนการกระจายตัวของอินสแตนซ์ที่เฉพาะเจาะจง ตัวอย่างเช่น ใน ปัญหา planted cliqueอินพุตคือกราฟสุ่มที่สุ่มตัวอย่างโดยการสุ่มกราฟสุ่ม Erdős–Rényiแล้ว "ปลูก" -clique แบบสุ่ม กล่าวคือเชื่อมต่อโหนดสุ่มอย่างสม่ำเสมอ (โดยที่) และเป้าหมายคือการค้นหา-clique ที่ปลูก (ซึ่งมีเอกลักษณ์ whp) ^{[ 20 ]}ตัวอย่างที่สำคัญอีกประการหนึ่งคือสมมติฐานของFeige ซึ่งเป็นสมมติฐานความยากในการคำนวณเกี่ยวกับอินสแตนซ์แบบสุ่มของ 3-SAT (สุ่มตัวอย่างเพื่อรักษาสัดส่วนเฉพาะของข้อความต่อตัวแปร) ^{[ 21 ]}สมมติฐานความยากในการคำนวณกรณีเฉลี่ยมีประโยชน์สำหรับการพิสูจน์ความยากในกรณีเฉลี่ยในแอปพลิเคชันเช่นสถิติ ซึ่งมีการกระจายตัวตามธรรมชาติของอินพุต^{[ 22 ]}นอกจากนี้ สมมติฐานความยากของคลิกที่ถูกปลูกฝังยังถูกนำมาใช้เพื่อแยกแยะความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดระหว่างพหุนามและกึ่งพหุนามของปัญหาอื่นๆ^{[ 23 ]}ในลักษณะเดียวกับสมมติฐานเวลาแบบเอกซ์โพเนนเชียล ${\displaystyle k}$${\displaystyle k}$${\displaystyle 2\log _{2}n\ll k\ll {\sqrt {n}}}$${\displaystyle k}$

ปัญหาการครอบคลุมป้ายกำกับที่ไม่ซ้ำกันเป็นปัญหาความพึงพอใจของข้อจำกัด โดยที่ข้อจำกัดแต่ละข้อเกี่ยวข้องกับตัวแปรสองตัวและสำหรับแต่ละค่าของจะมีค่าที่ไม่ซ้ำกัน ของ ที่สอดคล้องกับ การพิจารณาว่าข้อจำกัดทั้งหมดสามารถเป็นไปตามเงื่อนไขได้หรือไม่นั้นง่าย แต่สมมติฐานเกมที่ไม่ซ้ำกัน (UGC) ตั้งสมมติฐานว่าการพิจารณาว่าข้อจำกัดเกือบทั้งหมด ( เศษส่วน - สำหรับค่าคงที่ใดๆ) สามารถเป็นไปตามเงื่อนไขได้หรือไม่ หรือแทบจะไม่มีข้อจำกัดใดเลย ( เศษส่วน -) ที่สามารถเป็นไปตามเงื่อนไขได้นั้นเป็นปัญหา NP-hard ^{[ 16 ]}ปัญหาการประมาณค่ามักเป็นที่ทราบกันว่าเป็น NP-hard โดยสมมติว่า UGC เป็นไปตามเงื่อนไข ปัญหาดังกล่าวเรียกว่า UG-hard โดยเฉพาะอย่างยิ่ง เมื่อสมมติว่า UGC เป็นไปตามเงื่อนไข จะมีอั ลกอริทึม การเขียนโปรแกรมแบบกึ่งกำหนดที่รับประกันการประมาณค่าที่เหมาะสมที่สุดสำหรับปัญหาสำคัญหลายปัญหา^{[ 24 ]}${\displaystyle C}$${\displaystyle x,y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle C}$${\displaystyle (1-\varepsilon )}$${\displaystyle \varepsilon >0}$${\displaystyle \varepsilon }$

ปัญหาการครอบคลุมป้ายกำกับที่ไม่ซ้ำกันมีความเกี่ยวข้องอย่างใกล้ชิดกับปัญหาการขยายเซตขนาดเล็ก (SSE) : กำหนดกราฟ ให้หาเซตของจุดยอดขนาดเล็ก (ขนาด) ที่ มี การขยายขอบน้อยที่สุด เป็นที่ทราบกันว่าหาก SSE ยากที่จะประมาณค่าได้ การครอบคลุมป้ายกำกับที่ไม่ซ้ำกันก็ยากเช่นกัน ดังนั้นสมมติฐานการขยายเซตขนาดเล็กซึ่งตั้งสมมติฐานว่า SSE ยากที่จะประมาณค่าได้ จึงเป็นสมมติฐานที่แข็งแกร่งกว่า (แต่มีความเกี่ยวข้องอย่างใกล้ชิด) มากกว่าสมมติฐานเกมที่ไม่ซ้ำกัน^{[ 25 ]}ปัญหาการประมาณค่าบางอย่างเป็นที่ทราบกันว่ายากแบบ SSE ^{[ 26 ]} (เช่น ยากอย่างน้อยเท่ากับการประมาณค่า SSE) ${\displaystyle G=(V,E)}$${\displaystyle n/\log(n)}$

เมื่อกำหนดชุดตัวเลข ปัญหา 3SUM จะถามว่ามีชุดตัวเลขสามตัวที่มีผลรวมเป็นศูนย์หรือไม่ มี อัลกอริทึมแบบ ใช้เวลาเชิงกำลังสองสำหรับ 3SUM และมีการตั้งข้อสันนิษฐานว่าไม่มีอัลกอริทึมใดที่สามารถแก้ปัญหา 3SUM ได้ใน "เวลาที่ต่ำกว่ากำลังสองอย่างแท้จริง": ข้อสันนิษฐาน 3SUMคือสมมติฐานความยากในการคำนวณที่ว่าไม่มีอัลกอริทึมแบบใช้เวลา - สำหรับ 3SUM (สำหรับค่าคงที่ใดๆ) ข้อสันนิษฐานนี้มีประโยชน์สำหรับการพิสูจน์ขอบเขตล่างที่ใกล้เคียงกับกำลังสองสำหรับปัญหาหลายอย่าง ส่วนใหญ่มาจากเรขาคณิตเชิงคำนวณ^{[ 27 ]}${\displaystyle n}$${\displaystyle O(n^{2-\varepsilon })}$${\displaystyle \varepsilon >0}$

• ระดับความปลอดภัย