In this general talk I will discuss the complexity of NP-complete combinatorial search problems for several computational models, such as DPLL algorithms, Greedy algorithms, Linear and Semidefinite relaxations. I will survey several lower bounds for these models and discuss how the expansion of the underlying graph affects the computational intractability of the search problem.