MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-097

Enunciado: Dadas duas linguagens L₁, L₂ ⊆ {0,1}*, e dois algoritmos: A₁ que decide a linguagem L₁ e A₂ que decide a linguagem L₂, e denotando por T(X) a função que dá a complexidade de pior caso do algoritmo X, podemos afirmar que:

1. Se L₁ ≤p L₂, então T(A₁) = O(T(A₂))
2. Se  L₁ ≤p L₂, então L₁ ∈ NP implica L₂  ∈ P
3. Se T(A₁) = Ω(T(A₂)) e A₂ roda em tempo polinomial então L₁ ≤p L₂
4. Se L₁ ∈ P e A₁ também decidir L₂, então L₂ ∈ NP
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos