Metraipolis › archive › dc_e3cdee0ada80

Ipotesi del tempo esponenziale — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Ipotesi_del_tempo_esponenziale
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-06T09:15:25.296Z
SHA-256 of the archived text
cdab295c176e907cdf5deb891d2026d6a8ba7662fa4a5134fc642256789f31dd
Stable URL of this page
https://metraipolis.com/documento/dc_e3cdee0ada80

How to cite

Ipotesi del tempo esponenziale — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Ipotesi_del_tempo_esponenziale (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_e3cdee0ada80 (Metraipolis archive dc_e3cdee0ada80, sha256 cdab295c176e907cdf5deb891d2026d6a8ba7662fa4a5134fc642256789f31dd)
BibTeX
@misc{dce3cdee0ada80,
  title = {Ipotesi del tempo esponenziale — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Ipotesi_del_tempo_esponenziale},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_e3cdee0ada80; sha256 cdab295c176e907cdf5deb891d2026d6a8ba7662fa4a5134fc642256789f31dd},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Ipotesi_del_tempo_esponenziale. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Nella teoria della complessità computazionale, l'ipotesi del tempo esponenziale è un'assunzione di difficoltà computazionale non dimostrata, formalizzata da Impagliazzo & Paturi (1999), che afferma che 3-SAT (o uno qualsiasi dei vari problemi NP-completi) non possono essere risolti in tempo subesponenziale nel caso peggiore. L'ipotesi del tempo esponenziale, se fosse vera, implicherebbe che P ≠ NP. Essa può essere usata per dimostrare che molti problemi computazionali sono equivalenti in complessità, nel senso che se uno di essi ha un algoritmo in tempo subesponenziale, allora lo hanno tutti. Nell'ottobre 2026, le aziende statunitensi di intelligenza artificiale OpenAI e Anthropic hanno annunciato di aver ottenuto risultati che confuterebbero l'ETH, e un gruppo di esperti ha annunciato inoltre una collaborazione volta a esaminare tali risultati. Il risultato di OpenAI comprende in particolare una dimostrazione verificabile automaticamente secondo cui il relativo algoritmo richiede 2O(n(loglogn)2logn) passi.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «Ipotesi del tempo esponenziale» — https://it.wikipedia.org/wiki/Ipotesi_del_tempo_esponenziale
Wikidata Q5421532: «unproven computational hardness assumption that 3-SAT isn’t solvable in subexponential time in the worst case» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5421532
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Ipotesi_del_tempo_esponenziale?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 153090209, consultata il 2026-11-06T09:11:18.164Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: dff72924bbe18f2f01fe727f2f639d443a5058cb8c0be029de9e905040650a09