In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement. It implies that many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do, and that many known algorithms for these problems have optimal or near-optimal time complexity.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Exponential time hypothesis (en)
- Ipotesi del tempo esponenziale (it)
- 指数時間仮説 (ja)
- Гипотеза об экспоненциальном времени (ru)
- Hipótese do tempo exponencial (pt)
|
| rdfs:comment
| - In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement. It implies that many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do, and that many known algorithms for these problems have optimal or near-optimal time complexity. (en)
- 計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいてでは解けないというものである。 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。 (ja)
- Nella teoria della complessità computazionale, l'ipotesi del tempo esponenziale è un'assunzione di difficoltà computazionale non dimostrata, formalizzata da , 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. (it)
- Na teoria da complexidade computacional, a hipótese de tempo exponencial é uma suposição computacional de dureza não comprovada, formalizada por Impagliazzo e Paturi (1999), afirmando que o 3-SAT (ou qualquer um dos vários relacionados com problemas NP-completos) não pode ser resolvido em tempo subexponencial no pior caso. A hipótese de tempo exponencial, se verdadeira, implicaria que P ≠ NP. Ele pode ser usado para mostrar que muitos problemas computacionais são equivalentes em complexidade, no sentido de que, se um deles tem um algoritmo de tempo subexponencial, então todos eles fazem. (pt)
- Гипотеза об экспоненциальном времени — это недоказанное , которое сформулировали Импальяццо и Патури. Гипотеза утверждает, что 3-SAT (или любая из связанных NP-полных задач) не может быть решена за субэкспоненциальное время в . Из верности гипотезы об экспоненциальном времени, если она верна, следовало бы, что P ≠ NP, но гипотеза является более сильным утверждением. Из утверждения гипотезы можно показать, что многие вычислительные задачи эквиваленты по сложности в том смысле, что если одна из них имеет алгоритм экспоненциального времени, то все они имеют алгоритмы такой же сложности. (ru)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement. It implies that many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do, and that many known algorithms for these problems have optimal or near-optimal time complexity. (en)
- 計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいてでは解けないというものである。 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。 (ja)
- Nella teoria della complessità computazionale, l'ipotesi del tempo esponenziale è un'assunzione di difficoltà computazionale non dimostrata, formalizzata da , 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. (it)
- Na teoria da complexidade computacional, a hipótese de tempo exponencial é uma suposição computacional de dureza não comprovada, formalizada por Impagliazzo e Paturi (1999), afirmando que o 3-SAT (ou qualquer um dos vários relacionados com problemas NP-completos) não pode ser resolvido em tempo subexponencial no pior caso. A hipótese de tempo exponencial, se verdadeira, implicaria que P ≠ NP. Ele pode ser usado para mostrar que muitos problemas computacionais são equivalentes em complexidade, no sentido de que, se um deles tem um algoritmo de tempo subexponencial, então todos eles fazem. (pt)
- Гипотеза об экспоненциальном времени — это недоказанное , которое сформулировали Импальяццо и Патури. Гипотеза утверждает, что 3-SAT (или любая из связанных NP-полных задач) не может быть решена за субэкспоненциальное время в . Из верности гипотезы об экспоненциальном времени, если она верна, следовало бы, что P ≠ NP, но гипотеза является более сильным утверждением. Из утверждения гипотезы можно показать, что многие вычислительные задачи эквиваленты по сложности в том смысле, что если одна из них имеет алгоритм экспоненциального времени, то все они имеют алгоритмы такой же сложности. (ru)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)