Dois problemas de busca são estudados: o problema de busca num conjunto parcialmente ordenado e o problema de otimização de consultas em bases de dados com predicados caros. Provamos que o primeiro problema é NP-difícil e apresentamos algoritmos polinomiais que fornecem aproximações de maneira assintoticamente quase certa. Para o segundo problema cotas justas inferiores de desempenho são apresentadas para algoritmos determinísticos e aleatorizados, bem como algoritmos determinísticos e aleatorizados que atingem ou aproximam essas cotas. Diversas variantes do problema são consideradas.

not available