Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Exponential_time_hypothesis> ?p ?o. }
Showing items 1 to 29 of
29
with 100 items per page.
- Exponential_time_hypothesis abstract "In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption formalized by Impagliazzo & Paturi (1999) stating that 3-SAT (or any of several related NP-complete problems) cannot be solved in subexponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP. It can be used to show 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.".
- Exponential_time_hypothesis wikiPageExternalLink contents.html.
- Exponential_time_hypothesis wikiPageExternalLink paper.pdf.
- Exponential_time_hypothesis wikiPageExternalLink SODA11_060_lokshtanovd.pdf.
- Exponential_time_hypothesis wikiPageExternalLink exact.pdf.
- Exponential_time_hypothesis wikiPageID "26434552".
- Exponential_time_hypothesis wikiPageRevisionID "604577069".
- Exponential_time_hypothesis hasPhotoCollection Exponential_time_hypothesis.
- Exponential_time_hypothesis subject Category:Computational_hardness_assumptions.
- Exponential_time_hypothesis type Abstraction100002137.
- Exponential_time_hypothesis type Communication100033020.
- Exponential_time_hypothesis type ComputationalHardnessAssumptions.
- Exponential_time_hypothesis type Message106598915.
- Exponential_time_hypothesis type Postulate106753299.
- Exponential_time_hypothesis type Premise106753800.
- Exponential_time_hypothesis type Proposition106750804.
- Exponential_time_hypothesis type Statement106722453.
- Exponential_time_hypothesis comment "In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption formalized by Impagliazzo & Paturi (1999) stating that 3-SAT (or any of several related NP-complete problems) cannot be solved in subexponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP.".
- Exponential_time_hypothesis label "Exponential time hypothesis".
- Exponential_time_hypothesis label "Hipótese do tempo exponencial".
- Exponential_time_hypothesis label "Ipotesi del tempo esponenziale".
- Exponential_time_hypothesis sameAs Ipotesi_del_tempo_esponenziale.
- Exponential_time_hypothesis sameAs Hipótese_do_tempo_exponencial.
- Exponential_time_hypothesis sameAs m.0ds9b6x.
- Exponential_time_hypothesis sameAs Q5421532.
- Exponential_time_hypothesis sameAs Q5421532.
- Exponential_time_hypothesis sameAs Exponential_time_hypothesis.
- Exponential_time_hypothesis wasDerivedFrom Exponential_time_hypothesis?oldid=604577069.
- Exponential_time_hypothesis isPrimaryTopicOf Exponential_time_hypothesis.