A maior rede de estudos do Brasil

Grátis
271 pág.
Apostila LF

Pré-visualização | Página 49 de 49

concluir então que, se L2 ∈ C e L1 ≤P L2, então L1 ∈ C. Desta forma,
podemos dizer que, se existe uma redução polinomial de L1 para L2, então L1
é “não mais complexa” do que L2, ou, em outras palavras, L2 é “ao menos tão
complexa” quanto L1.
258 15. INTRODUÇÃO À TEORIA DA COMPLEXIDADE
DEFINIÇÃO 15.23. Seja C uma classe de complexidade e L uma linguagem.
Dizemos que L é C-Difícil se, para toda linguagem L′ ∈ C, existe uma redução
polinomial de L′ para L. Desta forma, L ser C-Difícil significa que L é ao menos
tão complexa quanto qualquer linguagem de C.
DEFINIÇÃO 15.24. Seja C uma classe de complexidade e L uma linguagem.
Dizemos que L é C-Completa se:
(1) L é C-Difícil e
(2) L ∈ C.
Desta forma, uma linguagem C-Completa é uma linguagem de C que é ao
menos tão complexa quanto qualquer linguagem de C, o que nos permite pensar
nas linguagens C-Completas como as linguagens mais complexas dentro da classe
C, ou o “limite superior” de complexidade dentro da classe.
Se sabemos que uma linguagem L é C-Completa, podemos provar que uma
outra linguagem L′ também é C-Completa mostrando que L′ ∈ C e que existe uma
redução polinomial f de L para L′. Como L é C-Completa, existe uma redução
polinomial de qualquer linguagem em C para L. Logo, compondo estas reduções
polinomiais com f , temos reduções polinomiais de qualquer linguagem em C para
L′, o que significa que L′ é C-Completa.
Acredita-se fortemente que P 6= NP, mas isto não foi provado. Um indício
forte da validade desta desigualdade vem do estudo dos problemas NP-Completos.
TEOREMA 15.25. P = NP se e somente se existe uma linguagem L NP-
Completa tal que L ∈ P.
DEMONSTRAÇÃO. (⇒) Suponha que P = NP e que L é uma linguagem NP-
Completa. Queremos mostrar que L ∈ P. Pela condição (2) da definição 15.24, se
L é NP-Completa, então L ∈ NP. Mas como estamos assumindo a hipótese de que
NP = P, então L ∈ P, como queríamos mostrar.
(⇐) Seja L uma linguagem NP-Completa tal que L ∈ P. Queremos mostrar
que P = NP. Como L ∈ P, L pode ser decidida por uma máquina de Turing
4. REDUÇÃO POLINOMIAL ENTRE LINGUAGENS 259
determinística polinomialmente limitada M . Por outro lado, pela condição (1) da
definição 15.24, se L é NP-Completa, então L é NP-Difícil. Por sua vez, se L é
NP-Difícil, então, para toda linguagem L′ ∈ NP, existe uma redução polinomial
de L′ para L, que pode ser computada por uma Máquina de Turing determinística
polinomialmente limitada M ′. Mas então a composição das Máquinas de Turing
M ′ e M também resulta em uma Máquina de Turing determinística polinomial-
mente limitada. Esta máquina decide L′, o que significa que L′ ∈ P . Como esta
argumentação vale para qualquer L′ ∈ NP , temos então que P = NP .
O primeiro problema que foi determinado como sendo NP-Completo foi o pro-
blema de determinar de uma dada fórmula da lógica proposicional é satisfatível, no
teorema de Cook. A partir de então, através do uso de reduções polinomiais, mui-
tos outros problemas foram caracterizados como NP-Completos. Até hoje, nenhum
algoritmo polinomial foi descoberto para nenhum dos problemas NP-Completos, o
que nos faz acreditar fortemente que os problemas NP-Completos não estão em P,
o que é equivalente a P 6= NP.
Outro resultado relacionado aos problemas NP-Completos diz respeito à igual-
dade ou diferença entre as classes NP e co-NP.
LEMA 15.26. Seja C uma classe de complexidade. Se C ⊆ co-C, então
C = co-C.
DEMONSTRAÇÃO. De acordo com o lema 15.20, se C ⊆ co-C, então co-C ⊆
co-(co-C) = C. Assim, a partir de C ⊆ co-C e co-C ⊆ C, podemos concluir que
C = co-C.
TEOREMA 15.27. NP = co-NP se e somente se existe uma linguagem L
NP-Completa tal que L ∈ co-NP.
DEMONSTRAÇÃO. (⇒) Suponha que NP = co-NP e que L é uma linguagem
NP-Completa. Pela condição (2) da definição 15.24, se L é NP-Completa, então
L ∈ NP. Mas como estamos assumindo a hipótese de que NP = co-NP, então
L ∈ co-NP, como queríamos mostrar.
260 15. INTRODUÇÃO À TEORIA DA COMPLEXIDADE
(⇐) Seja L uma linguagem NP-Completa tal que L ∈ co-NP. Pela condição
(1) da definição 15.24, seL é NP-Completa, entãoL é NP-Difícil. Por sua vez, seL
é NP-Difícil, então, para toda linguagem L′ ∈ NP, existe uma redução polinomial
de L′ para L, que pode ser computada por uma Máquina de Turing determinística
polinomialmente limitada M ′. Esta redução é dada por uma função polinomial-
mente computável f tal que w ∈ L′ ⇔ f(w) ∈ L. Esta função f também oferece
então uma redução polinomial entre L′ e L, da seguinte forma:
w ∈ L′ ⇔ w /∈ L′ ⇔ f(w) /∈ L⇔ f(w) ∈ L.
Como temos, por hipótese, que L ∈ co-NP, então L ∈ NP. Assim, existe uma
Máquina de Turing não-determinística polinomialmente limitada que decide L.
Mas então a composição das Máquinas de Turing M ′ e M também resulta em
uma máquina de Turing não-determinística polinomialmente limitada. Esta má-
quina decide L′, o que significa que L′ ∈ NP. Desta forma, podemos concluir que
L′ ∈ co-NP. Como esta argumentação vale para qualquer L′ ∈ NP, temos então a
seguinte conclusão: se L′ ∈ NP, então L′ ∈ co-NP. Isto, por sua vez, significa que
NP ⊆ co-NP. Este resultado, em conjunto com o lema acima, nos permite concluir
que NP = co-NP.
5. Exercícios
(1) Justifique cada uma das inclusões abaixo:
(a) P ⊆ NP
(b) NP ⊆ EXPTIME
(c) P ⊆ PSPACE
(d) PSPACE ⊆ EXPTIME
(2) Explique por que P = co− P, PSPACE = co− PSPACE e EXPTIME =
co− EXPTIME.
(3) Seja C uma classe de complexidade. Explique o que é uma linguagem
C-Difícil e o que é uma linguagem C-Completa.
5. EXERCÍCIOS 261
(4) Mostre que P = NP se e somente se existe uma linguagem NP-Completa
L tal que L ∈ P.
(5) Mostre que NP = co-NP se e somente se existe uma linguagem L NP-
Completa tal que L ∈ co-NP.
Referências Bibliográficas
[1] M. A. Harrison, Introduction to formal language theory, Addison-Wesley (1978).
[2] J. E. Hopcroft, J. D. Ullman e R. Motwani, Introdução à Teoria de Autômatos, Linguagens e
Computação, Tradução da 2a edição americana, Campus/Elsevier (2002).
[3] H. R. Lewis e C. H. Papadimitriou, Elementos de Teoria da Computação, 2a edição revisada,
Bookman (2004)
[4] M. Sipser, Introdução à Teoria da Computação, Tradução da 2a edição norte-americana, Cen-
gage Learning (2007).
263

Crie agora seu perfil grátis para visualizar sem restrições.