Exponential time hypothesis
http://dbpedia.org/resource/Exponential_time_hypothesis an entity of type: WikicatComputationalHardnessAssumptions
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.
rdf:langString
計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいてでは解けないというものである。 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。
rdf:langString
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.
rdf:langString
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.
rdf:langString
Гипотеза об экспоненциальном времени — это недоказанное , которое сформулировали Импальяццо и Патури. Гипотеза утверждает, что 3-SAT (или любая из связанных NP-полных задач) не может быть решена за субэкспоненциальное время в . Из верности гипотезы об экспоненциальном времени, если она верна, следовало бы, что P ≠ NP, но гипотеза является более сильным утверждением. Из утверждения гипотезы можно показать, что многие вычислительные задачи эквиваленты по сложности в том смысле, что если одна из них имеет алгоритм экспоненциального времени, то все они имеют алгоритмы такой же сложности.
rdf:langString
rdf:langString
Exponential time hypothesis
rdf:langString
Ipotesi del tempo esponenziale
rdf:langString
指数時間仮説
rdf:langString
Гипотеза об экспоненциальном времени
rdf:langString
Hipótese do tempo exponencial
xsd:integer
26434552
xsd:integer
1117051216
rdf:langString
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.
rdf:langString
計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいてでは解けないというものである。 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。
rdf:langString
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.
rdf:langString
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.
rdf:langString
Гипотеза об экспоненциальном времени — это недоказанное , которое сформулировали Импальяццо и Патури. Гипотеза утверждает, что 3-SAT (или любая из связанных NP-полных задач) не может быть решена за субэкспоненциальное время в . Из верности гипотезы об экспоненциальном времени, если она верна, следовало бы, что P ≠ NP, но гипотеза является более сильным утверждением. Из утверждения гипотезы можно показать, что многие вычислительные задачи эквиваленты по сложности в том смысле, что если одна из них имеет алгоритм экспоненциального времени, то все они имеют алгоритмы такой же сложности.
xsd:nonNegativeInteger
21689