計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいてでは解けないというものである。 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。

Property Value
dbo:abstract
  • 計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいてでは解けないというものである。 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。 (ja)
  • 計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいてでは解けないというものである。 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。 (ja)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 3235394 (xsd:integer)
dbo:wikiPageLength
  • 6576 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 65813120 (xsd:integer)
dbo:wikiPageWikiLink
prop-ja:wikiPageUsesTemplate
dct:subject
rdfs:comment
  • 計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいてでは解けないというものである。 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。 (ja)
  • 計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいてでは解けないというものである。 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。 (ja)
rdfs:label
  • 指数時間仮説 (ja)
  • 指数時間仮説 (ja)
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is owl:sameAs of
is foaf:primaryTopic of