Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model
lower bounds on the number of comparisons
scientific article; zbMATH DE number 3809332