Statements (19)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
computational complexity hypothesis
|
| gptkbp:abbreviation |
gptkb:ETH
|
| gptkbp:citation |
Impagliazzo, Paturi, and Zane, 'Which Problems Have Strongly Exponential Complexity?', JCSS, 2001
|
| gptkbp:formedBy |
gptkb:Ramamohan_Paturi
gptkb:Russell_Impagliazzo 1999 Francisco Santhanam |
| gptkbp:generalizes |
strong exponential time hypothesis
|
| https://www.w3.org/2000/01/rdf-schema#label |
exponential time hypothesis
|
| gptkbp:implies |
P ≠ NP
strong exponential time hypothesis |
| gptkbp:relatedTo |
theoretical computer science
NP-complete problems |
| gptkbp:state |
3-SAT cannot be solved in subexponential time in the number of variables
|
| gptkbp:usedIn |
fine-grained complexity
parameterized complexity lower bounds for algorithms |
| gptkbp:bfsParent |
gptkb:P_vs_NP_Problem
|
| gptkbp:bfsLayer |
6
|