acs

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado os algoritmos A₁ que decide a linguagem L₁ e A₂ que decide a linguagem L₂ e L₁, L₂ ⊆ {0,1}* podemos afirmar que:

1. Se L₁ ≤p L₂, então A₁ tem o mesmo tempo assintótico que A₂
2. Se  L₁ ≤p L₂ então L₁ ∈ NP implica L₂  ∈ P
3. Seja T(x) o tempo do algoritmo x, se T(A₁) = O(T(A₂))  e T(A₂) é 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