Mostrar código-fonte de Suposições de dificuldade computacional

Na teoria da complexidade computacional{{Ill|en||Computational complexity theory|nlk=true}}, uma '''suposição de dificuldade computacional''' é a hipótese de que um problema específico não pode ser resolvido de forma eficiente (onde ''eficiência'' normalmente significa "em [[Complexidade de Tempo#Tempo Polinomial|tempo polinomial]]"). Não se sabe como provar a dificuldade (incondicional) para essencialmente qualquer problema útil. Em vez disso, os cientistas da computação contam com [[Redução (complexidade)|reduções]] para relacionar formalmente a dificuldade de um problema novo ou complicado à uma suposição de dificuldade computacional sobre um problema que é mais bem compreendido.

As suposições de dificuldade computacional são de particular importância na [[criptografia]]. Um dos principais objetivos da criptografia é criar primitivas criptográficas{{Ill|en||Cryptographic primitive|nlk=true}} com segurança comprovada{{Ill|en||Provable security|nlk=true}}. Em alguns casos, os protocolos criptográficos apresentam [[Informação teoricamente segura|segurança teórica da informação]]; [[One-time pad|a chave (ou cifra) de uso único]] é um exemplo comum. No entanto, a segurança teórica da informação nem sempre pode ser alcançada; nesses casos, os criptógrafos recorrem à segurança computacional. Em termos gerais, isso significa que esses sistemas são seguros ''assumindo que quaisquer adversários são limitados computacionalmente'', como todos os adversários são na prática.

As suposições de dificuldade computacional também são úteis para orientar projetistas de algoritmos: um [[algoritmo]] simples provavelmente não refutará uma suposição de dificuldade computacional bem estudada, como [[P versus NP|P ≠ NP]].

==Comparando suposições de dificuldade==
Os cientistas da computação têm diferentes maneiras de avaliar quais suposições de dificuldade são mais confiáveis.

===Força das suposições de dificuldade===
Dizemos que a suposição <math>A</math> é ''mais forte'' do que a suposição <math>B</math> quando <math>A</math> implica <math>B</math> (e o inverso é falso ou desconhecido). Em outras palavras, mesmo que a suposição <math>A</math> fosse falsa, a suposição <math>B</math> ainda poderia ser verdadeira, e os protocolos criptográficos baseados na suposição <math>B</math> ainda podem ser seguros para uso. Assim, ao desenvolver protocolos criptográficos, se espera poder provar a segurança usando as suposições ''mais fracas'' possíveis.

===Suposições de caso médio ''versus'' de pior caso===
{{VT|Melhor caso, pior caso e caso médio}}
Uma suposição de [[Complexidade de caso médio|caso médio]] diz que um problema específico é difícil na maioria das instâncias de alguma distribuição explícita, enquanto uma suposição de [[Complexidade de pior caso|pior caso]] apenas diz que o problema é difícil em ''algumas'' instâncias. Para um determinado problema, a dificuldade de caso médio implica a dificuldade de pior caso, portanto, uma [[#Suposições de dificuldade de caso médio|suposição de dificuldade de caso médio]] é mais forte do que uma suposição de dificuldade de pior caso para o mesmo problema. Além disso, mesmo para problemas incomparáveis, uma suposição como a [[#Hipótese de tempo exponencial (H.T.E.) e variantes|hipótese de tempo exponencial]] é frequentemente considerada preferível a uma [[#Suposições de dificuldade de caso médio|suposição de caso médio]] como a conjectura de clique oculto{{Ill|en||Planted clique|nlk=true}}.<ref name=BKW15>{{Cite conference |doi=10.1137/1.9781611973730.66 |isbn=978-1-61197-374-7 |contribution=''Approximating the best Nash equilibrium in <math>n^{o(\log(n))}</math>-time breaks the Exponential time hypothesis'' |title=Symposium on discrete algorithms (S.O.D.A.) |pages=970–982 |year=2015 |author1-link=Mark Braverman |first1=Mark |last1=Braverman |first2=Young Kun |last2=Ko |first3=Omri |last3=Weinstein |publisher=[[Society for Industrial and Applied Mathematics|''Sociedade para a matemática aplicada e industrial'']] |language=en }}</ref> Porém, para aplicações criptográficas, saber que um problema tem alguma instância difícil (o problema é difícil na pior das hipóteses) é inútil porque não nos fornece uma maneira de gerar instâncias difíceis.<ref name="katz07">J. Katz e Y. Lindell, ''Introduction to modern cryptography'' (''Chapman and Hall/CRC Cryptography and network security series'') (em inglês), ''Chapman and Hall/CRC'', 2007.</ref> Felizmente, muitas suposições de caso médio usadas em criptografia (incluindo [[#Problema RSA|RSA]], [[#Problema de logaritmo discreto (P.L.D.)|logaritmo discreto]] e alguns [[#Problemas de rede|problemas de rede]]) podem ser baseadas em suposições de pior caso por meio de reduções de pior caso a caso médio.<ref name=GK16>{{Cite conference |doi=10.1007/978-3-662-49096-9_21 |contribution=''Cryptographic assumptions: A position paper'' |title=Theory of cryptography conference (T.C.C.) 2016 |pages=505–522 |year=2016 |author1-link=Shafrira Goldwasser |first1=Shafi |last1=Goldwasser |author2-link=Yael Tauman Kalai |first2=Yael Tauman |last2=Kalai |publisher=''Springer'' <!-- |title-link=:en:International Association for Cryptologic Research#Theory of Cryptography -->|doi-access=free |language=en }}</ref>

===Falseabilidade===
Uma característica desejada de uma suposição de dificuldade computacional é a [[falseabilidade]], ou seja, se a suposição fosse falsa, então seria possível a provar. Em particular, {{Harvtxt|Naor|2003}} introduziu uma noção formal de falseabilidade criptográfica.<ref>{{Cite conference |last=Naor |first=Moni |editor-last=Boneh |editor-first=Dan |contribution=''On cryptographic assumptions and challenges'' |doi=10.1007/978-3-540-45146-4_6 |location=Berlim |mr=2093188 |pages=96–109 |publisher=''Springer'' |series=''Lecture notes in computer science'' |title=Advances in cryptology – CRYPTO 2003: 23rd annual international cryptology conference, Santa Barbara, California, USA, August 17–21, 2003, Proceedings |volume=2729 |year=2003 |doi-access=free |language=en }}</ref> [[Grosso modo]], uma suposição de dificuldade computacional é considerada falseável se puder ser formulada em termos de um desafio: um protocolo interativo entre um adversário e um verificador eficiente, onde um adversário eficiente pode convencer o verificador a aceitar [[se e somente se]] a suposição for falsa.

==Suposições comuns de dificuldade criptográfica==
Existem muitas suposições de dificuldade criptográfica em uso. Esta é uma lista de algumas das mais comuns e de alguns protocolos criptográficos que os utilizam.

===Fatoração de inteiros===
{{Artigo principal|Fatoração de inteiros}}
Dado um [[número composto]] <math>n</math>, e em particular aquele que é o produto de dois primos grandes <math>n = p\cdot q</math>, o problema de fatoração de inteiros é encontrar  <math>p</math> e <math>q</math> (mais geralmente, encontrar primos <math>p_1,\dots,p_k</math> de modo que <math>n = \prod_i p_i</math>). É um grande problema em aberto encontrar um algoritmo para fatoração de inteiros que execute em tempo polinomial no tamanho da representação (<math>\log(n)</math>). A segurança de muitos protocolos criptográficos se baseia na suposição de que a fatoração de inteiros é difícil (ou seja, não pode ser resolvida em tempo polinomial). Os criptosistemas cuja segurança é equivalente a esta suposição incluem o [[Criptossistema Rabin|criptosistema Rabin]] e o criptosistema Okamoto-Uchiyama{{Ill|en||Okamoto–Uchiyama cryptosystem|nlk=true}}. Muitos outros criptosistemas dependem de suposições mais fortes, como [[#Problema RSA|RSA]], [[#Problemas de residuosidade|problemas de residuosidade]] e [[#Suposição de ocultamento de Phi|ocultação de Phi]].

====Problema RSA====
{{Artigo principal|Problema RSA}}
Dado um número composto <math>n</math>, expoente <math>e</math> e número<math>c := m^e (\mathrm{mod}\; n)</math>, o problema RSA é encontrar <math>m</math>. O problema é considerado difícil, mas se torna fácil devido à fatoração de <math>n</math>. No [[RSA (sistema criptográfico)|criptosistema RSA]], <math>(n,e)</math> é a [[Criptografia de chave pública|chave pública]], <math>c</math> é a criptografia da mensagem <math>m</math> e a fatoração de <math>n</math> é a chave secreta usada para descriptografia.

====Problemas de residuosidade====
<!-- {{Artigo principal|:en:Higher residuosity problem}} -->
Dado um número composto <math>n</math> e inteiros <math>y,d</math>, o problema de residuosidade é determinar se existe (alternativamente, encontre um) <math>x</math> tal que
:<math> x^d \equiv y \pmod{n}.</math>

Casos especiais importantes incluem o problema de residuosidade quadrática{{Ill|en||Quadratic residuosity problem|nlk=true}} e o problema de residuosidade composta de decisão{{Ill|en||Decisional composite residuosity assumption|nlk=true}}. Como no caso do RSA, este problema (e seus casos especiais) são considerados difíceis, mas se tornam fáceis devido à fatoração de<math>n</math>. Alguns criptosistemas que dependem da dificuldade dos problemas de residuidade incluem:
* Criptosistema Goldwasser–Micali{{Ill|en||Goldwasser–Micali cryptosystem|nlk=true}} (problema de residuosidade quadrática)
* [[Blum Blum Shub|Gerador Blum Blum Shub]] (problema de residuosidade quadrática)
* Criptosistema Paillier{{Ill|en||Paillier cryptosystem|nlk=true}} (problema de residuosidade composta de decisão)
* Criptosistema Benaloh{{Ill|en||Benaloh cryptosystem|nlk=true}} (problema de maior residuosidade)
* Criptosistema Naccache-Stern{{Ill|en||Naccache–Stern cryptosystem|nlk=true}} (problema de maior residuosidade)

====Suposição de ocultamento de Phi====
<!-- {{Artigo principal|:en:Phi-hiding assumption}} -->
Para um número composto <math>m</math>, não se sabe como calcular eficientemente sua [[função totiente de Euler]] <math>\phi(m)</math>. A suposição de ocultação de Phi postula que é difícil calcular <math>\phi(m)</math> e, além disso, mesmo computar quaisquer fatores primos de <math>\phi(m)</math> é difícil. Essa suposição é usada no protocolo PIR Cachin–Micali–Stadler.<ref>{{Cite book |last1=Cachin |first1=Christian |last2=Micali |first2=Silvio|last3=Stadler|first3=Markus |title=Advances in cryptology — EUROCRYPT '99 |chapter=''Computationally private information retrieval with polylogarithmic communication'' |series=''Lecture notes in computer science'' |year=1999 |publisher=''Springer'' |volume=1592 |pages=402–414 |doi=10.1007/3-540-48910-X_28 |editor1-last=Stern |editor1-first=Jacques |isbn=978-3-540-65889-4 |s2cid=29690672 |language=en }}</ref>

===Problema de logaritmo discreto (P.L.D.)===
{{Artigo principal|Logaritmo discreto}}
Dados os elementos <math>a</math> e <math>b</math> de um [[Grupo (matemática)|grupo]] <math>G</math>, o problema de logaritmo discreto pede um inteiro <math>k</math> tal que <math>a=b^k</math>. O problema de logaritmo discreto não é conhecido por ser comparável à fatoração de inteiros, mas suas complexidades computacionais estão [[Logaritmo discreto#Comparação com a fatoração de inteiros|intimamente relacionadas]].

A maioria dos protocolos criptográficos relacionados ao problema de log discreto, na verdade, dependem da suposição de Diffie–Hellman{{Ill|en||Computational Diffie–Hellman assumption|nlk=true}} mais forte: determinados elementos de grupo <math>g, g^a, g^b</math>, onde <math>g</math> é um gerador e <math>a,b</math> são inteiros aleatórios, é difícil encontrar <math>g^{a\cdot b}</math>. Exemplos de protocolos que usam essa suposição incluem a [[troca de chaves de Diffie–Hellman]] original, bem como a [[El Gamal|criptografia ElGamal]] (que depende da variante decisória de Diffie–Hellman{{Ill|en||Decisional Diffie–Hellman assumption|nlk=true}} (''D.D.H.'') ainda mais forte).

====Mapas multilineares====
Um [[Função n-linear|mapa multilinear]] é uma função <math>e: G_1 ,\dots,G_n \rightarrow G_T</math> (onde <math>G_1 ,\dots,G_n,G_T</math> são [[Grupo (matemática)|grupos]]) tais que para qualquer <math>g_1, \dots, g_n \in G_1, \dots G_n</math> e <math>a_1, \dots, a_n</math>,
:<math>e(g_1^{a_1},\dots,g_n^{a_n}) = e(g_1,\dots,g_n)^{a_1\cdots a_n}</math>

Para aplicações criptográficas, gostaríamos de construir grupos <math>G_1 ,\dots,G_n,G_T</math> e um mapa <math>e</math> de modo que o mapa e as operações de grupo em <math>G_1 ,\dots,G_n,G_T</math> possam ser calculados de forma eficiente, mas o problema de logaritmo discreto em <math>G_1 ,\dots,G_n</math> ainda é difícil.<ref name=BS02>
{{Cite journal <!-- |author1-link=:en:Dan Boneh -->|first1=Dan |last1=Boneh <!-- |author2-link=:en:Alice Silverberg -->|first2=Alice |last2=Silverberg |year=2002 |title=''Applications of multilinear forms to cryptography'' |url=https://eprint.iacr.org/2002/080 |journal=Cryptology ePrint archive |language=en }}</ref> Algumas aplicações requerem suposições mais fortes, por exemplo, análogos multilineares das suposições de Diffie-Hellman.

Para o caso especial de <math>n=2</math>, mapas bilineares{{Ill|en||Bilinear map|nlk=true}} com segurança confiável foram construídos usando emparelhamento Weil{{Ill||en||Weil pairing|nlk=true}} e emparelhamento Tate{{Ill|en||Tate pairing|nlk=true}}.<ref name=DBS04>
{{Cite journal |first1=Ratna |last1=Dutta |first2=Rana |last2=Barua |first3=Palash |last3=Sarkar|year=2004 |title=''Pairing-based cryptographic protocols : A survey'' |url=https://eprint.iacr.org/2004/064 |journal=Cryptology ePrint archive |language=en }}</ref> Para <math>n>2</math> muitas construções foram propostas nos últimos anos, mas muitas delas também foram quebradas e, atualmente, não há consenso sobre um candidato seguro.<ref>
{{Cite web |url= http://malb.io/are-graded-encoding-schemes-broken-yet.html|title=''Are graded encoding scheme broken yet?'' |first= Martin R. |last=Albrecht |access-date=22-03-2018 |language=en }}</ref>
Alguns criptosistemas que dependem de suposições de dificuldade multilinear incluem:
* Esquema Boneh–Franklin{{Ill|en||Boneh–Franklin scheme|nlk=true}} (bilinear Diffie–Hellman)
* Boneh–Lynn–Shacham{{Ill|en||BLS digital signature|nlk=true}} (bilinear Diffie-Hellman)
* Garg-Gentry-Halevi-Raykova-Sahai-Waters candidato para ofuscação indistinguível{{Ill|en||Indistinguishability obfuscation|nlk=true}} e criptografia funcional{{Ill|en||Functional encryption|nlk=true}} (quebra cabeças multilinear)<ref>
{{Cite journal |first1=Sanjam |last1=Garg |first2=Craig |last2=Gentry |first3=Shai |last3=Halevi |first4=Mariana |last4=Raykova |first5=Amit |last5=Sahai |first6=Brent |last6=Waters |year=2016 |title=''Candidate indistinguishability obfuscation and functional encryption for all circuits'' |publisher=Sociedade de matemática industrial e aplicada (''S.I.A.M.'') |volume=45 |number=3 |pages=882–929 |url=https://eprint.iacr.org/2013/451.pdf |journal=<!-- [[:en:SIAM Journal on Computing]] -->S.I.A.M. journal on computing |doi=10.1137/14095772X |language=en }}</ref>

===Problemas de redes diagonais===
<!-- {{Artigo principal|:en:Lattice problem}} -->
O problema computacional mais fundamental nas redes diagonais é o problema de vetor mais curto{{Ill|en||Lattice problem#Shortest vector problem (SVP)|nlk=true}} (P.V.M.C.): dada uma rede <math>L</math>, encontrar o menor vetor <math>v \in L</math> diferente de zero. A maioria dos criptosistemas requer suposições mais fortes sobre as variantes do problema de vetor mais curto (P.V.M.C.), como o problema de vetores independentes mais curtos{{Ill|en||Lattice problem#Shortest independent vectors problem (SIVP)|nlk=true}} (''P.V.I.M.C.''), o ''GapSVP''{{Ill|en||Lattice problem#GapSVP|nlk=true}}<ref name=peikert09>{{Cite conference |first=Chris |last=Peikert |contribution=''Public-key cryptosystems from the worst-case shortest vector problem: extended abstract'' |doi=10.1145/1536414.1536461 |pages=333–342 |title=Proceedings on 41st annual A.C.M. symposium on theory of computing (S.T.O.C.) |year=2009 |language=en }}</ref> ou o ''Unique-SVP''.<ref name = ad97>{{Cite conference |author1-link=Miklós Ajtai |first1=Miklós |last1=Ajtai <!-- |author2-link=:en:Cynthia Dwork -->|first2=Cynthia |last2=Dwork |contribution=''A public-key cryptosystem with worst-case/average-case equivalence'' |doi=10.1145/258533.258604 |pages=284–293 |title=Proceedings on 29th annual A.C.M. Symposium on Theory of Computing (S.T.O.C.) |year=1997 |language=en }}</ref>

A suposição de dificuldade de rede mais útil em criptografia é para o problema de aprendizado com erros (A.C.E.): amostras fornecidas para <math>(x,y)</math>, onde <math>y=f(x)</math> para alguma função linear <math>f(\cdot)</math>, é fácil aprender <math>f(\cdot)</math> usando [[álgebra linear]]. No problema de aprendizado com erros (A.C.E.), a entrada para o algoritmo tem erros, ou seja, para cada par <math>y\neq f(x)</math> com alguma pequena probabilidade. Se acredita que os erros tornam o problema intratável (para parâmetros apropriados); em particular, existem reduções conhecidas de pior caso a caso médio de variantes do problema de vetor mais curto.<ref name=regev10>{{Cite conference |first=Oded |last=Regev |contribution=''The learning with errors problem (invited survey)'' |doi=10.1109/CCC.2010.26 |pages=191–204 |title=Conference on computational complexity (C.C.C.) 2010 |year=2010 <!-- |title-link=:en:Computational Complexity Conference -->|language=en }}</ref>

Para computadores quânticos, os problemas de fatoração e logaritimo discreto são fáceis, mas os problemas de rede são considerados difíceis.<ref name=peikert16>{{Cite journal |first=Chris |last=Peikert |year=2016|title=''A decade of lattice cryptography'' |url=https://eprint.iacr.org/2015/939 |journal=Foundations and trends in theoretical computer science |volume=10 |number=4 |pages=283–424 |doi=10.1561/0400000074 |language=en }}</ref> Isso torna alguns [[Criptografia baseada em reticulados|criptosistemas baseados em rede]] candidatos para [[criptografia pós-quântica]].

Alguns criptosistemas que dependem da dificuldade dos problemas de rede incluem:
* [[NTRU]] (NTRUEncrypt{{Ill|en||NTRUEncrypt|nlk=true}} e NTRUSign{{Ill|en||NTRUSign|nlk=true}})
* A maioria dos candidatos para [[Encriptação homomórfica|criptografia totalmente homomórfica]]

==Suposições de dificuldade que não é criptográfica==
Assim como suas aplicações criptográficas, as suposições de dificuldade são usadas na teoria da complexidade computacional{{Ill|en||Computational complexity theory|nlk=true}} para fornecer evidências para afirmações matemáticas que são difíceis de provar incondicionalmente. Nessas aplicações, prova-se que a suposição de dificuldade implica alguma afirmação teórica da complexidade desejada, em vez de provar que a afirmação em si é verdadeira. A suposição mais conhecida desse tipo é a suposição de que [[P versus NP|P ≠ NP]],<ref>{{Cite journal |first=Lance |last=Fortnow <!-- |author-link=:en:Lance Fortnow -->|url=http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf |archive-url=https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf |urlmorta=sim |archive-date=2011-02-24 |title=''The status of the P versus NP problem'' |journal=[[Communications of the ACM]] |volume=52 |year=2009 |issue=9 |pages=78–86 |doi=10.1145/1562164.1562186 |s2cid=5969255 |language=en }}</ref> mas outras incluem a [[Hipótese do tempo exponencial|hipótese de tempo exponencial]],<ref>{{Cite book |last=Woeginger |first=Gerhard <!-- |author-link=:en:Gerhard J. Woeginger -->|doi=10.1007/3-540-36478-1_17 |title=Combinatorial optimization — Eureka, you shrink! |pages=185–207 |publisher=Springer-Verlag |contribution=''Exact algorithms for NP-hard problems: A survey'' |year=2003 |volume=2570 |s2cid=289357 |language=en }}</ref> a conjectura clique plantado{{Ill|en||Planted clique|nlk=true}} e a [[conjectura de jogos únicos]].<ref name=khot10>{{Cite conference <!-- |author-link=:en:Subhash Khot -->|last=Khot |first=Subhash |contribution=''On the Unique games conjecture'' |title=Proc. 25th I.E.E.E. conference on Computational complexity  |url=http://cs.nyu.edu/~khot/papers/UGCSurvey.pdf |year=2010 |pages=99–121 |doi=10.1109/CCC.2010.19 |language=en }}</ref>

===Problemas difíceis de ''C''===
Muitos problemas computacionais de [[Complexidade de pior caso|pior caso]] são conhecidos por serem difíceis ou mesmo [[Completo (complexidade)|completos]] para alguma [[classe de complexidade]] <math>C</math>, em particular [[NP-difícil|difícil de ''NP'']] (mas frequentemente também difícil de ''PSPACE''{{Ill|en||List of PSPACE-complete problems|nlk=true}}, difícil de ''PPAD''{{Ill|en||List of PPAD-complete problems|nlk=true}}, etc.). Isso significa que eles são pelo menos tão difíceis quanto qualquer problema na classe <math>C</math>. Se um problema é <math>C</math>-difícil (com respeito às reduções de tempo polinomial), então não pode ser resolvido por um algoritmo de tempo polinomial, a menos que a suposição de dificuldade computacional <math>P \neq C</math> seja falsa.

===Hipótese de tempo exponencial (H.T.E.) e variantes===
{{Artigo principal|Hipótese do tempo exponencial}}
A hipótese de tempo exponencial (''eth'') é um [[#Força das suposições de dificuldade|reforço]] da suposição de dificuldade <math>P \neq NP</math>, que conjectura que não apenas o [[Problema de satisfatibilidade booliana|problema de satisfatibilidade booleana]] não tem um algoritmo de tempo polinomial, mas também requer tempo exponencial (<math>2^{\Omega(n)}</math>).<ref>{{Cite conference |last1=Impagliazzo |first1=Russell |author1-link=Russell Impagliazzo |last2=Paturi |first2=Ramamohan |contribution=''The complexity of k-SAT'' |doi=10.1109/CCC.1999.766282 |pages=237–240 |title=Proc. 14th I.E.E.E. conference on computational complexity |year=1999 |language=en }}</ref>  Uma suposição ainda mais forte, conhecida como [[Hipótese do tempo exponencial|hipótese de tempo exponencial forte]] (H.T.E.F.) conjectura que [[Problema de satisfatibilidade booliana|''SAT'' de <math>k</math>]] requer tempo <math>2^{(1-\varepsilon_k)n}</math>, onde <math>\lim_{k \rightarrow \infty} \varepsilon_k = 0</math>. Hipótese de tempo exponencial (H.T.E.), hipótese de tempo exponencial forte (H.T.E.F.) e pressupostos de dificuldade computacional relacionados permitem a dedução de resultados de complexidade refinados, por exemplo, resultados que distinguem o tempo polinomial e o tempo quase polinomial{{Ill|en||Quasi-polynomial time|nlk=true}},<ref name=BKW15/> ou mesmo <math>n^{1.99}</math> ''versus'' <math>n^2</math>.<ref>{{Cite conference |last1=Abboud |first1=Amir |last2=Vassilevska-Williams |first2=Virginia  |author2-link=Virginia Vassilevska Williams |last3=Weimann  |first3=Oren |contribution=''Consequences of faster alignment of sequences'' |doi=10.1007/978-3-662-43948-7_4 |pages=39–51 |title=Automata, languages, and programming - 41st International colloquium, I.C.A.L.P. 2014 |year=2014 |language=en }}</ref> Essas suposições também são úteis na [[complexidade parametrizada]].<ref name = LMS11>{{Cite journal |last1=Lokshtanov |first1=Daniel  |last2 = Marx  |first2 = Daniel |last3=Saurabh |first3=Saket |title=''Lower bounds based on the Exponential time hypothesis'' |journal=Bulletin of the E.A.T.C.S. |volume=105 |pages=41–72 |year=2011 |url= http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/96 |language=en }}</ref>

===Suposições de dificuldade de caso médio===
{{Artigo principal|Complexidade de caso médio}}
Alguns problemas computacionais são considerados difíceis em média em uma distribuição particular de instâncias. Por exemplo, no problema do clique plantado{{Ill|en||Planted clique|nlk=true}}, a entrada é um grafo aleatório amostrado, amostrando um [[Modelo Erdős–Rényi|grafo aleatório Erdős–Rényi]] e então "plantando" um clique <math>k</math> aleatório, ou seja, conectando nós <math>k</math> uniformemente aleatórios (onde <math>2\log_2 n \ll k \ll \sqrt n</math>), e o objetivo é encontrar o clique <math>k</math> plantado (que é, com alta probabilidade, único).<ref name="ab">{{Cite book |title=Computational complexity: A modern approach |first1=Sanjeev |last1=Arora |author1-link=Sanjeev Arora |first2=Boaz |last2=Barak |publisher=''Cambridge University Press'' |year=2009 |isbn=9780521424264 |pages=362–363 |url=https://books.google.com/books?id=8Wjqvsoo48MC&pg=PA362 |language=en }}</ref> Outro exemplo importante é a hipótese de [[Uriel Feige|Feige]], que é uma suposição de dificuldade computacional sobre instâncias aleatórias de [[Problema de satisfatibilidade booliana|''SAT'' de 3]] (amostradas para manter uma proporção específica de cláusulas para variáveis).<ref name=Feige02>{{Cite conference |last1=Feige |first1=Uriel |author1-link=Uriel Feige |contribution=''Relations between average case complexity and approximation complexity'' |doi=10.1145/509907.509985 |pages=534–543 |title=Proceedings on 34th annual A.C.M. symposium on theory of computing (S.T.O.C.) |year=2002 |language=en }}</ref> As suposições de dificuldade computacional de caso médio são úteis para provar a dificuldade de caso médio em aplicações como estatísticas, onde há uma distribuição natural sobre as entradas.<ref name=BR13>
{{Cite conference |last1=Berthet |first1=Quentin |last2=Rigollet |first2=Philippe |contribution=''Complexity theoretic lower bounds for sparse principal component detection'' |pages=1046–1066 |title=C.O.L.T. 2013 |url=http://jmlr.org/proceedings/papers/v30/Berthet13.html |year=2013 |language=en }}</ref> Além disso, a suposição de dificuldade do clique plantado também foi usada para distinguir entre a complexidade de tempo de pior caso polinomial e quase polinomial de outros problemas,<ref name=HK11>{{Cite journal |last1=Hazan |first1=Elad |last2=Krauthgamer |first2=Robert |title=''How hard is it to approximate the best Nash equilibrium?'' |doi=10.1137/090766991 |pages=79–91 |journal=<!-- SIAM Journal on Computing -->S.I.A.M. journal on computing |volume=40 |number=1 |year=2011 |citeseerx=10.1.1.139.7326 |language=en }}</ref> de forma semelhante à [[#Hipótese de tempo exponencial (H.T.E.) e variantes|hipótese de tempo exponencial]].

===Jogos únicos===
{{Artigo principal|Conjectura de jogos únicos}}
O problema de [[Conjectura de jogos únicos#Cobertura de etiqueta única|cobertura de rótulo exclusivo]] é um problema de satisfação de restrição, onde cada restrição <math>C</math> envolve duas variáveis <math>x,y</math>, e para cada valor de <math>x</math> há um valor único de <math>y</math> que satisfaz <math>C</math>. Determinar se todas as restrições podem ser satisfeitas é fácil, mas a conjectura de jogos únicos (C.J.U.) postula que determinar se quase todas as restrições (fração <math>(1-\varepsilon)</math>, para qualquer constante <math>\varepsilon>0</math>) podem ser satisfeitas ou quase nenhuma delas (fração  <math>\varepsilon</math>) podem ser satisfeitas é difícil de ''NP'.<ref name=khot10/> Os problemas de aproximação são frequentemente conhecidos como difíceis de ''NP'' assumindo conjectura de jogos únicos (C.J.U.); tais problemas são chamados de difícil de jogos únicos (J.U.). Em particular, assumindo conjectura de jogos únicos (C.J.U.), há um algoritmo de programação semidefinida{{Ill|en||Semidefinite programming|nlk=true}} que atinge garantias de aproximação ótimas para muitos problemas importantes.<ref name=rag08>
{{Cite conference |first=Prasad |last=Raghavendra |contribution=''Optimal algorithms and inapproximability results for every C.S.P.?'' |doi=10.1145/1374376.1374414 |pages=245–254 |title=40th annual A.C.M. symposium on theory of computing (S.T.O.C.) 2008 |year=2008 |language=en }}</ref>

====Expansão de conjunto pequeno====
<!-- {{Artigo principal|:en:Small set expansion hypothesis}} na enwiki -->
Intimamente relacionado ao problema de cobertura de rótulo único está o '''problema de expansão de conjunto pequeno (E.C.P.)''': Dado um gráfico <math>G = (V,E)</math>, encontrar um conjunto pequeno de vértices (de tamanho <math>n/\log(n)</math>) cuja expansão de borda{{Ill|en||Expander graph#Edge expansion|nlk=true}} é mínima. Se sabe que, se a expansão de conjunto pequeno é difícil de estimar, o mesmo ocorre com a cobertura de rótulo único. Consequentemente, a hipótese de expansão de conjunto pequeno, que postula que a expansão de conjunto pequeno é difícil de se aproximar, é uma suposição mais forte (mas intimamente relacionada) do que a conjectura de jogo único.<ref name=rs10>{{Cite conference |first1=Prasad |last1=Raghavendra |first2=David |last2=Steurer |contribution=''Graph expansion and the Unique games conjecture'' |doi=10.1145/1806689.1806792 |pages=755–764 |title=42nd annual A.C.M. symposium on theory of computing (S.T.O.C.) 2010 |year=2010 |language=en }}</ref> Alguns problemas de aproximação são conhecidos por serem difíceis de expansão de conjunto pequeno (E.C.P.)<ref>{{Cite journal |first1=Yu |last1=Wu |first2=Per |last2=Austrin |first3=Toniann |last3=Pitassi |first4=David |last4=Liu |title=''Inapproximability of Treewidth and related problems'' |doi=10.1613/jair.4030 |pages=569–600 |journal= Journal of artificial intelligence research |volume=49 |year=2014 |doi-access=free |language=en }}</ref> (ou seja, pelo menos tão difíceis quanto aproximar a expansão de conjunto pequeno).

===A conjectura ''3SUM''===
<!-- {{Artigo principal|3SUM}} -->
Dado um conjunto de <math>n</math> números, o problema ''3SUM'' pergunta se existe um trio de números cuja soma é zero. Há um algoritmo de tempo quadrático para ''3SUM'', e foi conjecturado que nenhum algoritmo pode resolver ''3SUM'' em "tempo verdadeiramente subquadrático": a conjectura ''3SUM'' é a suposição de dificuldade computacional de que não há algoritmos de tempo <math>O(n^{2-\varepsilon})</math> para ''3SUM'' (para qualquer constante <math>\varepsilon > 0</math>). Esta conjectura é útil para provar limites inferiores quase quadráticos para vários problemas, principalmente de [[geometria computacional]].<ref>{{Cite conference |last1=Vassilevska Williams |first1=Virginia |author1-link=Virginia Vassilevska Williams |contribution=''On some fine-grained questions in algorithms and complexity'' |title=I.C.M. 2018 |url=http://people.csail.mit.edu/virgi/eccentri.pdf |year=2018 |language=en }}</ref>

==Ver também==
* Nível de segurança{{Ill|en||Security level|nlk=true}}

{{Referências}}
<!-- {{Computational hardness assumptions}} -->
[[Categoria:Algoritmos]]
[[Categoria:Suposições de dificuldade computacional]]
[[Categoria:Teoria da criptografia]]