MO417 - Questão para a prova oral

Número: 106

Enunciado:
Sabemos (provamos) que a melhor complexidade de qualquer algoritmo que resolve um problema A é Ω(nlgn), e conhecemos uma redução de qualquer instância a do problema A para alguma instância b do problema B, e que essa transformação leva tempo O(n). Lembre-se que uma redução só é valida se a solução de b para o problema B é igual à solução de a para o problema A

Podemos afirmar então que:

1. Certamente existe um algoritmo para resolver o problema B que é o(nlgn)
2. Qualquer algoritmo que resolve A, certamente também resolve B.
3. Se existir um algoritmo para resolver o problema B, certamente é Ω(nlgn)
4. Se provarmos que qualquer algoritmo para resolver B é Ω(n²), então qualquer algoritmo para resolver A é também é Ω(n²).
5. NDA

Autor(a): Pedro Henrique Del Bianco Hokama