Statements (23)
Predicate | Object |
---|---|
gptkbp:instanceOf |
computational complexity hypothesis
|
gptkbp:abbreviation |
gptkb:ETH
|
gptkbp:category |
theoretical computer science
hypotheses in computer science |
gptkbp:citation |
gptkb:Impagliazzo_and_Paturi,_2001,_Journal_of_Computer_and_System_Sciences
|
gptkbp:field |
theoretical computer science
|
https://www.w3.org/2000/01/rdf-schema#label |
Exponential Time Hypothesis
|
gptkbp:implies |
gptkb:Strong_Exponential_Time_Hypothesis
P ≠ NP |
gptkbp:proposedBy |
gptkb:Ramamohan_Paturi
gptkb:Russell_Impagliazzo 2001 |
gptkbp:relatedTo |
gptkb:3-SAT_problem
gptkb:Satisfiability_problem gptkb:Strong_Exponential_Time_Hypothesis NP-complete problems computational lower bounds |
gptkbp:state |
3-SAT cannot be solved in subexponential time in the number of variables
|
gptkbp:usedIn |
parameterized complexity
fine-grained complexity theory lower bounds for algorithms |
gptkbp:bfsParent |
gptkb:Complexity_theory
|
gptkbp:bfsLayer |
6
|