MO417 - Questão para a prova oral

Número: 2010-106

Enunciado: Suponha que foi provado que qualquer algoritmo que decide uma certa linguagem A roda em tempo Ω(n lg n), e suponha que conhecemos uma redução de A para a linguagem B que leva tempo O(n).  Aqui n sempre se refere ao tamanho da entrada.

Podemos então afirmar que:

1. Certamente existe um algoritmo para decidir B que é o(n lg n).
2. Qualquer algoritmo que decide A certamente também decide B.
3. Se existir um algoritmo para decidir a linguagem B, certamente roda em tempo Ω(n lg n)
4. Se provarmos que qualquer algoritmo para decidir B roda em tempo Ω(n²), então qualquer algoritmo para decidir A também rodará em tempo Ω(n²).
5. NDA

Ideia original de: Pedro Henrique Del Bianco Hokama