a) A classe de problemas em P consiste nos problemas que dado um "certificado" de uma solução, é possível verificar se a solução é correta em tempo polinomial no tamanho da entrada.
ERRADO. Essa é a definição da classe NP
b) A classe de problemas NP consiste nos problemas que não pertencem a classe P, e por isso são problemas não "verificáveis" em tempo polinomial.
ERRADO. A classe NP contém a classe P e é a classe de problemas verificáveis em tempo polinomial, segundo a definição em a).
c) A busca binária é um problema em NP-completo, dependendo do tamanho da entrada.
ERRADO. A busca binária é um problema da classe P, pois possui complexidade O(log n)
d) Um problema que está em P não estará em NP, exceto problemas NP-completos, os quais não foram demonstrados pela ciência.
ERRADO. A classe P está contida em NP.
e) Dado que exista um problema NP-completo com solução em tempo polinomial, então todos os problemas em NP terão soluções em tempo polinomial.
CERTO. Dentro da classe NP-completo, todos os problemas podem ser reduzidos uns aos outros. Logo, se algum deles tiver solução em tempo polinomial, todos terão.