فرضیه سختی محاسباتی
فرضیات سختی غیررمزنگاری > فرضیه 3SUM

مقاله اصلی: 3SUM
در مسئله 3SUM، با یک مجموعه از n عدد روبه‌ رو هستیم و هدف این است که آیا سه عدد وجود دارند که مجموع آن‌ ها صفر شود؟ یک الگوریتم زمانی درجه دوم برای 3SUM وجود دارد و فرض شده که هیچ الگوریتمی نمی‌تواند 3SUM را در زمان “واقعاً کمتر از درجه دوم” حل کند. فرضیه 3SUM یک فرض سختی محاسباتی است که بیان می‌کند هیچ الگوریتم ‌O(n^(2-\u03b5)) (برای هر مقدار ثابت ε>0) برای حل 3SUM وجود ندارد. این فرضیه برای اثبات کران‌ های پایین نزدیک به درجه دوم در مسائل مختلف، به‌ ویژه در هندسه محاسباتی، مفید است.
1 2  "Computational hardness assumption". Wikipedia (به انگلیسی). 2023-12-20.
↑  Braverman, Mark; Ko, Young Kun; Weinstein, Omri (2015-10). "Approximating the best Nash Equilibrium in  n o   (log n )  -time breaks the Exponential Time Hypothesis" (به انگلیسی). Society for Industrial and Applied Mathematics: 970–982. doi:10.1137/1.9781611973730.66. ISBN 978-1-61197-374-7. {{cite journal}}: Cite journal requires |journal= (help); Check date values in: |date= (help)
↑  J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/CRC Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.
↑  Goldwasser, Shafi; Kalai, Yael Tauman (2016). "Cryptographic Assumptions: A Position Paper". Theory of Cryptography Conference (TCC) 2016. Springer. pp. 505–522. doi:10.1007/978-3-662-49096-9_21.
↑  Naor, Moni (2003). "On cryptographic assumptions and challenges". In Boneh, Dan (ed.). Advances in Cryptology – CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings. Lecture Notes in Computer Science. Vol. 2729. Berlin: Springer. pp. 96–109. doi:10.1007/978-3-540-45146-4_6. MR 2093188.
↑  Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2016-01). "Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits". SIAM Journal on Computing (به انگلیسی). 45 (3): 882–929. doi:10.1137/14095772X. ISSN 0097-5397. {{cite journal}}: Check date values in: |date= (help)
↑  Ajtai, Miklós; Dwork, Cynthia (1997). "A public-key cryptosystem with worst-case/average-case equivalence" (به انگلیسی). ACM Press: 284–293. doi:10.1145/258533.258604. ISBN 978-0-89791-888-6. {{cite journal}}: Cite journal requires |journal= (help)
↑  Fortnow, Lance (2009-09). "The status of the P versus NP problem". Communications of the ACM (به انگلیسی). 52 (9): 78–86. doi:10.1145/1562164.1562186. ISSN 0001-0782. {{cite journal}}: Check date values in: |date= (help)
↑  Lokshtanov, Daniel; Marx, Daniel; Saurabh, Saket (2011). "Lower bounds based on the Exponential Time Hypothesis". Bulletin of the EATCS. 105: 41–72.
↑  Feige, Uriel (2002-05-19). "Relations between average case complexity and approximation complexity" (به انگلیسی). ACM: 534–543. doi:10.1145/509907.509985. ISBN 978-1-58113-495-7. {{cite journal}}: Cite journal requires |journal= (help)
↑  Berthet, Quentin; Rigollet, Philippe (2013-08-01). "Optimal detection of sparse principal components in high dimension". The Annals of Statistics. 41 (4). doi:10.1214/13-aos1127. ISSN 0090-5364.
↑  Hazan, Elad; Krauthgamer, Robert (2011-01). "How Hard Is It to Approximate the Best Nash Equilibrium?". SIAM Journal on Computing (به انگلیسی). 40 (1): 79–91. doi:10.1137/090766991. ISSN 0097-5397. {{cite journal}}: Check date values in: |date= (help)
↑  Raghavendra, Prasad (2008-05-17). "Optimal algorithms and inapproximability results for every CSP?" (به انگلیسی). ACM: 245–254. doi:10.1145/1374376.1374414. ISBN 978-1-60558-047-0. {{cite journal}}: Cite journal requires |journal= (help)
↑  Raghavendra, Prasad; Steurer, David (2010-06-05). "Graph expansion and the unique games conjecture" (به انگلیسی). ACM: 755–764. doi:10.1145/1806689.1806792. ISBN 978-1-4503-0050-6. {{cite journal}}: Cite journal requires |journal= (help)
↑  Wu, Y.; Austrin, P.; Pitassi, T.; Liu, D. (2014-04-06). "Inapproximability of Treewidth and Related Problems". Journal of Artificial Intelligence Research. 49: 569–600. doi:10.1613/jair.4030. ISSN 1076-9757.
↑  WILLIAMS, VIRGINIA VASSILEVSKA (2019-05). "ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY". Proceedings of the International Congress of Mathematicians (ICM 2018). WORLD SCIENTIFIC. doi:10.1142/9789813272880_0188. {{cite journal}}: Check date values in: |date= (help)