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.