Complexidade Computacional,
Lógica e
Teoria da Prova
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
É mais fácil verificar uma solução do que calculá-la ???
f(x) =
1 => Para se escrever
|x|
02
02
|x|
a partir de x se usa “tempo” exponencial.
2 => Para, dados <x,y>, verificar-se se f(x) = y usa-se “tempo” polinomial
1 => Para se encontrar uma valoração que satisfaça uma fórmula booleana
parece precisar-se de “tempo” exponencial.
2 => Dada uma fórmula e uma valoração, verifica-se em “tempo” polinomial
se esta satisfaz a fórmula,.
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
PVp = { f / f(a1,...,ak)= b é verificável em tempo poli para
toda <a1,...,ak,b> }
PCp = { f / f(a1,...,ak) é calculável em tempo poli para
toda <a1,...,ak>}
Teorema : PVp  PCp se e somente se P = NP
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Qual a relação entre a Lógica e a Computação ?
-
O que é a (Teoria da) Computação ?
(Tentativa de) conceituação do
Computável
-
O que é Lógica ?
(Tentativa de) conceituação do
Razoável
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Razoável
Todo evento que é passível de uma
explicação, na forma argumentativa,
construída sobre fatos iniciais
inquestionáveis.
Antes de 1879
Ago/2003
Lógica Aristotélica e Escolástica (a partir de 300 a.c.)

====>  Álgebras Booleanas (Boole 1847)
 Álgebra Relacional (DeMorgan, Schroeder,
C.S.Peirce XIX)
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Evolução da Lógica como assunto matemático
DeMorgan (1830) Observa que a álgebra não necessita lidar tão somente
com conceitos numéricos.
Boole (1854) Descreve uma álgebra a partir de operações entre conjuntos
e relações lógicas, confirmando DeMorgan.
Frege (1879) estabele a lógica como um sistema formal que tem sua
linguagem particular e distinta da natural. O conceito de prova
matemática passa a ser formal.
Frege (1884) busca a fundamentação da aritmética em bases puramente
lógicas , com a adição do conceito de pertinência () como
primitivo.
===> Os paradoxos aparecem novamente !!
===> Paradoxos associados ao axioma da escolha, etc
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Principais Resultados em Lógica/Metamatemática no início do século XX
- Teoria dos Tipos como solução ao paradoxo em Russell
- Russell e Whitehead publicam o Principia Mathematica.
- Presburger (1929) prova que a aritmética sem a multiplicação é decidível.
- Skolem (1931) prova que a aritmética sem a adição e o sucessor é decidível
- Herbrand (1931) prova a consistência de um fragmento fraco da aritmética
(só o sucessor).
-Tarski (1930) formaliza a semântica adequada para a lógica de primeira ordem
- Gödel (1930) prova a completude do cálculo de primeira ordem
- Gödel (1931) introduz a idéia de aritmetizar (codificar na forma numérica) a linguagem
de um sistema formal de forma que (meta) teoremas do sistema possam ser vistos como
teoremas aritméticos e prova seu famoso teorema da incompletude. Obs: # é o código
de .
- Gödel (1931) prova a não-provabilidade da consistência.
- Gentzen (1936) prova a consistência da aritmética ( Haupsatz para o Cálculo de Sequentes)
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Computável
Toda tarefa que pode ser realizada
por um ser burro com um mínimo
de conhecimento/capacidade.
burro = Incapaz de Aprender
conhecimento = ?
 Máquina de Raciocinar (Leibniz 1667)
Antes de 1900 d.c ====>  Máquina de Calcular de Pascal .l (Pascal sec.XVII)
 Máquina de Babbage (Ch. Babbage. sec. XIX)
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
A Computação do ponto de vista das funções recursivas
1931 - Gödel define as funções prim. recursivas associando-as a provas em aritmética
1927/1928 - Ackermann define uma função que necessita de recursão simultânea
1934 - Rózsa Péter - Prova que as funções prim. recursivas formam a classe definida por
recursão simples e “nested” a partir de funções iniciais constantes, identidade e a função
sucessor. Prova que a função de Ackermann é na realidade definida por recursão em
duas variáveis e não é portanto primitivamente recursiva, mas é computável.
1936 - A. Turing - Define uma máquina formal a partir de princípios simples (ler , apagar e
escrever símbolos em uma fita) e define o conceito de Máquina Universal. Prova que
não existe máquina capaz de verificar se outra máquina pára ou não. Desde o início a
sua máquina com versão Não-Determinística
1936 - A. Church Define o -Calculus e mostra que este é capaz de definir todas as funções
para as quais existe uma Máquina de Turing.
1938 - Kleene Define, aceitando que o computável inclui a parcialidade funcional, as funções
parcialmente recursivas e lança a Tese de Church.
1954 - Markov Estabele o conceito de computável com base em identificação de palavras e
símbolos (algoritmos de Markov) e justifica o ponto de vista finitista da computação.
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Sxyz  (xy)xz
:0:  I :1:  P0K
Kxy  x
Ix  x (I SKK)
:2:  P1K ..... :n:  P:n-1:K ....
P
Tese de Church: f: N  N é computável se e somente se
existe um combinador FC1 C2... Cn tal que para todo nN
(F:n:  :m:)
f(n) = m)
f é
recursiva
n
existe uma máquina de Turing M , tal que M com 11.......111
na fita de entrada M pára com 11.....11111 na saída sss nf(n) = m
existe um algoritmo de Markov A , m
t.q. A lendo 11.......111
pára e produz o string
11.....11111 na saída sss f(n) = m
m
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
A Máquina de Turing
- Modelo determinístico
’
q q’
Máquina Universal U
U(i,a) = Ti(a)
- Modelo multi-cabeça (determinístico)
Ago/2003
i1
i2
ik
qi1
qi2
qik
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
M. Turing modelo multi-fita (determinístico)
i1
1
qi1
i
2
2
qi2
i
k
k
qik
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
A partir da década de 50 (sec. XX).......
algoritmo
Sequência de
passos
Conjunto de
sequência de
passos
não-determinismo
paralelismo
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
determinismo
paralelismo c/
sincronia
TECMF
A Máquina de Turing (cont.)
- Modelo não-determinístico

q


q1
q2

q3



q11
q12
q13


Ago/2003


Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler

TECMF

Medindo a eficiência de algoritmos
- Escolha do modelo
- Recursos: Tempo x Memória
- Relacionando os algoritmos e os problemas que estes resolvem
- Computação de Funções
- Problemas de otimização
- Problemas de decisão,
- Linguagens
- Classes de complexidade: Como defini-las ???
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Problemas de Decisão
sim
x
xP?
não
1
|x|  *
Prog.
0
Problemas de Decisão  Linguagens Formais
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Algumas Definições
L  DTime(f)
sss
 m  TuringDet t.q.
(m decide L) e c, x  Strings
steps(m,x)  cf(|x|)
L  DSpace(f)
sss
 m  TuringDet t.q.
(m decide L) e c, x  Strings
space(m,x)  cf(|x|)
- Como medir espaço (memória) ???
- Qualquer tipo de função serve como parâmetro de medida ??
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Por que considerar classes assintóticas de funções ??
Teorema: (speedup linear) Se uma linguagem L é decidida em tempo f(n) então
para qualquer  > 0 existe uma M. Turing M que decide L em tempo
.f(n) + n + 2.
Prova : Modificar o tamanho da “palavra” de memória
Consequências do seedup:
Se L é decidida em tempo f(n) = 165.nk + .... + 54.n + 657
então L é decidida em tempo f’(n) = nk
Obs: O mesmo teorema ( e técnica de prova) vale para função de medida e uso de
espaço (número máximo de células visitadas)
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Funções de tempo construtivas
Fato: Existe f, tal que, DTime(f) = Dtime(2f)
Def. f é uma funçao de tempo construtível, sss, existe uma máquina de Turing
M tal que para todo n, M(1n) = 1f(n) e steps(M, 1n)  cf(n).
Propriedades :
- Para qualquer função computável g existe uma função de tempo construtível f tal que g < f.
- As funçoes polinomiais, exponencial e logaritmos (inteiros) são funções
de tempo construtíveis
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
As funções step e
space
- space deve levar a entrada em consideração ?
- step deve levar a leitura da entrada em consideração ?
- O modelo (M.T.) tem alguma robustez com relação as medidas ?
- O que acontece quando modifica-se o número de cabeças ?
Fato: Se L é reconhecida em tempo O(f) em uma MT com mais de uma cabeça,
então L é reconhecida em tempo O(f2) em uma MT com uma cabeça.
- O que acontece quando modifica-se o número de fitas ?
Fato: Se L é reconhecida em tempo O(f(|x|)) em uma MT com uma fita,
então L é reconhecida em tempo O((1/2k)f(|x|)+ |x|) em uma MT
com k fitas
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Algumas propriedades e definições:
Se f é de tempo construtível então :
coDTime(f) = { L /  m  TuringDet t.q. (m decide Lc) e x  Strings
steps(m,x)  O(f(|x|)) }
Fato I: DTime(f) =coDTime(f)
Fato II: Se n  f(n) e |L1L2| finito então L1  DTime(f) sss L1  DTime(f)
Fato III: DTime(f) é construtivamente enumerável, i.e., existe uma MT T
tal que T(i,x) = Ti(x) e DTime(f) = {Li / Ti decide Li }.
Def. P =  DTime(ni)
iN
Ago/2003
i
Def. EXP =  DTime(2n )
iN
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Teorema de Cantor
{A / A  B}
==> Seja B um conjunto, então |B| < |2B|
Prova: Suponha que |B| = |2B| então existe f: B  2B
S = { x / x  f(x) }
f-1(S)  S se e somente se f-1(S)  S
Paradoxo do Barbeiro: Em uma cidade existe um barbeiro que faz a barba de
todos os homens que não barbeiam a sí próprios e somente
estes.
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
O método da diagonal de Cantor
suponha que |(0,1)| = |N|
a0= 0, aoo ao1 ao2 ao3 ao4....... aon..............
a1= 0, a1o a11 a12 a13 a14....... a1n..............
5
se ajj = 9
9
senão
b j=
an= 0, ano an1 an2 an3 an4....... ann..............
b = 0,b0 b1 b2 b3 b4....... bn.........
|(0,1)|  |N|
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Hierarquia própria de funções construtivas
Paraf = { <T,x> / T(x) pára no máximo em f(|x|) passos}
FatoI : Paraf  DTime(f3)
FatoII : Paraf  DTime(f(x/2))
Prova: Diagonalização
Corolário I : DTime(f(n))  DTime(f(2n+1)3)
Corolário II : P  EXP
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Classes de Complexidade e algumas relações
Def. PSpace =  DSpace(ni)
iN
Def. NP =  NTime(ni )
iN
Def. NPSpace =  NSpace(ni)
iN
Def. Log = Space(log) e NLog = NSpace(log)
Log  NLog  P  NP  NSpace
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
- DSpace(f(n))  NSpace(f(n)) e DTime(f(n))  NTime(f(n))
- NTime(f(n))  DSpace(f(n))
- NSpace(f(n))  DTime(klog n + f(n)) (obs; Número de conf. + alcançabilidade)
- Alcançabilidade  Space(log2)
- número de nós alcançavel  Space(log) =>
Ago/2003
NSpace(f)  Space(f2)
NSpace(f) = coNSpace(f)
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
A Ciência da Computação Hoje : NP = P ? (Cook 1971)
P : Encontra solução em tempo polinomial
NP : Verifica solução em tempo polinomial
CoNP : Verifica que não é solução, em tempo polinomial
Taut  CoNP
Sat  NP
Verificação de Modelos
Prova de Teoremas
Obs: Se CoNP  NP então NP  P
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Def. Seja C uma classe de problemas (linguagens). Diz-se que um problema (ling.)
P é C-completo (a) se e somente se todo problema (ling) de C é redutível a P.
Isto é resolver P é tão difícil quanto resolver qualquer outro problema em C.
Exemplos:
- Saber se um programa pára (via outro programa) é Rec-Completo, onde
Rec é o conjunto dos problemas (ling) recursivos.
- Saber se dado uma solução para um problema esta é verificável em tempo
polinomial é tão difícil quanto decidir se uma sentença da lógica proposicional é
“verdadeira”. Sat é NP-completa.
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
decidir se
uma
fórmula
da lógica
prop é
Sat
decidir se uma
fórmula da
lógica de
predicados é Sat
O(2n)
decidir primalidade
NP
NPC ?
P
decidir se
uma
3CNF
fórmula
é Sat
O(n3)
O(n2)
decidir se 2
cláusulas de Horn
prop são equiv.
decidir se uma
2CNF é Sat
O(n)
decidir se uma
cláusula de Horn
prop é Sat
Obs: Supondo P  NP
Alguns Fatos Importantes :
Fato 1: Existe um oráculo B tal que PB = NPB
Prova: NPSPACE=PSPACE e B um problema NPSPACE completo
Fato 2: Existe um oráculo C tal que PC  NPC
Prova: Diagonalização
Discussão : Simulação e Diagonalização para provar P = NP ??
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Fato : Se PNP então NP-NPC  .
Prova: Diagonalização Uniforme [Ladner 1975]
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Lema: Sejam C1 e C2 duas classes de Linguagens, tais que :
1- C1 e C2 são construtivamente enumeráveis
2- C1 e C2 são fechadas para variação finita
3-Existe L1 C1 e L2  C2
nestas condições existe L, tal que:
L  C1  C2
e
L  L1  L2
Prova: Diagonalização
Teorema: Se PNP, então Sat  P e   NPC então existe
L  P  NPC
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
A representação influencia a complexidade de um problema ??
Alfabetos ??
Teorema: Se alguma linguagem unária for NP-completa então P=NP.
Prova :
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Hierarquia de Kleene
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Hierarquia Polinomial
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Circuitos Booleanos
=> Dígrafos acíclicos com nós AND, OR, NOT, nós iniciais (sem arco
entrante) e um e somente um nó terminal (sem saída).
5
Exemplo: Circuito para computar alcançabilidade em
grafos. Entrada = <Grafo, <1,n>>
Gij = matriz de adjacências de um dígrafo
2
1
3
4
Ago/2003
12345
101001
200010
310000
400000
510000
01001
00010
10000
00000
10000
direto





pass. por 1.










pass. por 1 ou
direto.



pass. por 2
(poss. por 1 tb)
pass. por 2,1 ou
direto.


Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler

TECMF
pass. por 5,4,3,
2,1 ou direto.
Famílias de Circuitos Booleanos
Def. L é decidida por uma família (Ci)iN, sss, para todo string s, com
|s| = n, Cn aceita s se e somente se s  L.
Questão : O tamanho de um circuito tem a ver com a complexidade (em MT) do
problema de decisão associado ???
Resp. : Prox. Slides
Obs: => Alcançabilidade tem circuitos de tamanho O(n3) e profundidade
O(n)
Conjectura: Todo problema de decisão com famílias de circuitos de tamanho
polinomial é um problema que está em P ??
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Resp: NÃO
=> Problemas indecidíveis tem famílias polinomiais de circuitos booleanos
Exemplo: Seja D  {1}* uma linguagem indecidível. e seja (Ai)iN a família de
circuitos tal que
- se 1k D
- se 1k D
Ago/2003
então Ak é o circuito só com portas AND e k fontes
então Ak é o circuito com só portas AND e uma NOT ao final.
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Famílias Uniformes de Circuitos Booleanos
Fato: NLSpace  P
(klog(n) = n)
Def. Uma família (Ci)iN de circuitos booleanos é uniforme, sss, existe uma MT
(não determinística) que para entrada 1n gera o circuito Cn usando log(n)
células da fita.
==> Alcançabilidade possui família uniforme de circuitos booleanos
- Dado n, existe uma MT para gerar Cn usando somente log(n) de espaço na fita
de trabalho.
==> Gerar todos os circuitos de profundidade n com n2 nós fontes
e verificar se a forma é a requerida.
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Nova Conjectura: P = Linguagens aceitas por famílias uniformes de Circuitos
booleanos de tamanho polinomial ??
Desta vez SIM.
Prova: Construção usada na prova que SAT é NP-completo e definição de
família uniforme de Circuitos de tamanho polinomial.
() Trivial
() Seja L P, então existe uma MT det. M que decide L em tempo
nk. Seja w  L, tal que |w|=n. Da tabela de computação de M
constrói-se um circuito Cn.
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Tabela de computação de M para a entrada w
q01
2
s11 s12...... s1m s21 s22...... s2m
n-1
n   ....
s
s(n-1)1 s(n-1)2...... s(n-1)m n1 s12...... snm
xx-1
x
x+1
tempo t
tempo t+1
x
nk
ad1 ad2...... adm
a11 a12...... a1m a21 a22...... a2m
’1
’2
a(p-1)1 a(p-1)2...... a(p-1)m at1 a12...... apm
’p-1
qj’2
b11 b12...... b1m b21 b22...... b2m
A
Ago/2003
C
|w|=n
E
I
T
A
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
  ....
TECMF
’p   ....
Observações:
1- O tamanho do circuito
Pad
só depende de M.
Se  = Est(M)  Alfa(M)  {,} e c = || então |Pad| = 3.c
2- w  L, se e somente se, o circuito tem valor “true” quando “alimentado”
com cod(w).
3- O construção de um circuito C|w| é feita a partir de M e |w| usando espaço de
ordem log(|w|) na fita. Algoritmo imprime na fita de saída as diversas cópias de
Pad (tamanho independente da entrada), com as respectivas junções de e/s que
usam espaço de ordem log(|w|) .
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Proposição: Toda linguagem em P possui família uniforme de circuitos booleanos
de tamanho polinomial.
Corolário: SE existe L NP é tal que toda família uniforme de circuitos que
decide L não tem tamanho limitada por nenhum polinômio ENTÃO PNP
Um caminho para provar PNP :
==> Provar que algum problema NP-completo possui cota inferior
superpolinomial
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Circuitos x Circuitos monotônicos
- Circuitos monotônicos são aqueles construídos sem o uso da porta NOT.
Def. Uma função booleana f é monotônica, se e somente se, se a b então
f(x1,...,a,...,xn)  f(x1,...,b,...,xn).
Obs I: Todo circuito monotônico computa uma função monotônica
Obs II: O circuito utilizado na demonstração da conjectura é monotônico,
ou seja, o problema (P-completo) de avaliar um circuito é redutível
via circuitos monotônicos. (Expressividade !!!!!)
Exemplos:
- Alcançabilidade, circuito hamiltoniano e clique são monotônicos,
- Mochila e cobertura euleriana não são monotônicos
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Circuitos ingênuos monotônicos para computar CLIQUEn,k
2
1
1
100101010
1
i1
1
n
i
vi1 100101010
k
n-1
100101010
n
1
n
1
i
i1
k
v j 100101010
100101010
1
n
n
i1
1
n
i
k
vik 100101010
100101010
n
i
  ... 
  ... 
  ... 
  ...    ... 

S = { vi1 ,....., vik }
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
n
Circuitos “ingênuos” monotônicos para computar CLIQUEn,k
2
1
1
100101010
1
n
100101010
n-1
1
n
S1
100101010
S
100101010
(k )
OR
Ago/2003
1
n
Sn
j
Def. CC(S1, ..., Sm)
é o circuito ingênuo
construído a partir dos
conjuntos S1, ..., Sm de
vértices
n
Tamanho = k2 ( n )
k
2n
Obs: 2n < ( )
n
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
n
Teorema do Razborov
Teorema: Circuitos monotônicos para CLIQUEn,k , quando k = 4n,
tem cota inferior :
c8 n 

O 2 


Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Esquema:
1 - Considerar um circuito monotônico qualquer C
=> Considerar tipos particulares de exemplos negativos e positivos
para teste de clique (exemplos em quantidade exponencial)
2- Aproximar C via um circuito ingênuo CC(S1, ..., Sm) introduzindo
um número pequeno (poli) de falsos positivos e de falsos negativos.
3- Cada aproximação é executada sobre uma porta (gate) do circuito.
4- Demonstra-se que o circuito ingênuo resultante da aplicação de “3”
a todas as portas de C tem uma quantidade exponencial de
falsos positivos e de falsos negativos.
5- Concluí-se que C só pode ter uma quantidade exponencial de portas.
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Exemplos positivos e exemplos negativos
Exemplo positivo:
- Um grafo simples com n vértices contendo um subgrafo completo de
tamanho k
=> Existem (
n
) exemplos positivos.
k
Exemplo negativo:
- Um grafo com n? vértices e (k-1) colorável
=> Existem (k-1)n exemplos negativos
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Resultado de combinatória importante para o teorema
Lema de Erdös-Rado: Seja F uma família de com mais que
M=(p-1)L.L! conjuntos, todos não vazios e todos com cardinalidade
máxima L. Então F contêm um “girassol”.
Z>M
Z1
Z2
ZZ = Z Z
i
Z3
j
k
= Núcleo
v
Z
j
Prova: Por indução em L
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Construção Indutiva do circuito aproximante para C.
Caso Base: C =gij , porta de entrada
gij
Aprox(C)=
CC({gij})
Casos Indutivos:
1- C = C1 OR C2
Aprox(C1)=CC(F1) e Aprox(C2)=CC(F2)
Aprox(C) = CC(F1F2)
Obs: Manter a cardinalidade dos geradores do circuito ingênuo.
- Se | F1F2| > M substituir os elementos do “girassol” pelo seu núcleo
Aprox(C) = CC(Nu(F1F2))
se usamos M=(p-1)L.L! =>
Ago/2003
forçamos a existência de “girassois” com pétalas
de tamanho L
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
2- C = C1 AND C2
Aprox(C1) = CC(F1) ,
Aprox(C2) = CC(F2)
Aprox(C) = CC(Nu({XY: X F1, Y  F2 e |X Y| L}))
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Lema I : Em cada aproximação são introduzidos no máximo M22-p(k-1)n
falsos positivos
Lema II: Cada aproximação introduz no máximo
negativos
M 2(
n-L-1
k-L-1
) falsos
Lema III: Todo circuito aproximante ou é idêntico ao circuito “falso” ou
resulta em “verdadeiro” em pelo menos metade dos exemplos
negativos.
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
O que é introduzir falsos positivos ou falsos negativos ??
Obs: No caso base da construção do circuito aproximante (Aprox({gij}) =
CC({gij}) , a aproximação é exata !!!!!
- Se C = C1 OR C2 , Aprox(Ci)=CC(Fi) , CC(Fi) retorna “verd” para algum i
quando alimentado com um exemplo positivo G, e, Aprox(C) retorna “falso”
quando alimentado com G.
=> Aprox(C) introduziu um falso negativo
- Se C = C1 OR C2 , Aprox(Ci)=CC(Fi) , CC(Fi) retorna “falso” para algum i
quando alimentado com um exemplo negativo G, e, Aprox(C) retorna “verd”
quando alimentado com G.
=> Aprox(C) introduziu um falso positivo
- Similar para C=C1 AND C2
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Lema I : Em cada aproximação são introduzidos no máximo M22-p(k-1)n
falsos positivos
- C = C1 OR C2 com Aprox(Ci)=CC(Fi) e Aprox(C) = CC(Nu(F1F2))
A introdução de falsos positivos é culpa do operador Nu.
=> Substituir (Z1,....,Zp) , um “girassol”, por Z, seu núcleo, em F1F2.
- G é falso positivo , então .......
Z
p
Z1
Z2 Z  F1
Z1 Z3 Zj  F2
Z2
p
Z3
Quantas cores diferentes pode haver no Núcleo ???
Z
j
Ago/2003
=> Qual a probabilidade de se colorir todos os
vértices em G com repetição e o núcleo não ????
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Rep(X) = Há cores repetidas em X.
=
prob(Rep(Z1) & ..... & Rep(Zp) &  Rep(Z))  prob((Rep(Z1) & ..... & Rep(Zp))|  Rep(Z))
prob( Rep(Z))
p
p
=  prob(Rep(Zi)|  Rep(Z))   prob(Rep(Zi))  2-p
i=1
i=1
8
L
| Zi |
(n)!
L!
8
(n
-2)! 2!  1/2
(L-2)! 2!
2
2
=


Rep(Zi) =
4
n
-1
k-1
k-1
k-1
Estimativa de falsos positivos na
porOR
operação
aproximação
Nu
 2-p. (k-1)n 2M/(p-1)
colorações possíveis
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
operações
Nu
2- C = C1 AND C2
Aprox(C1) = CC(F1) ,
Aprox(C2) = CC(F2)
Aprox(C) = CC(Nu({XY: X F1, Y  F2 e |X Y| L}))
não introduz falsos positivos
pode retirar
positivos mas nunca
incluir falsos positivos
Pode incluir no máximo 2-p falsos positivos por operação de Nu
Estimativa de falsos positivos para a aproximação AND  2-p (k-1)n M2
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
n-L-1
Lema II: Cada aproximação introduz no máximo M2( k-L-1
negativos
) falsos
1 - A operação Nu não introduz falsos negativos.
=> A aproximação para OR não introduz falsos neg.
2- C = C1 AND C2
CC({XY/X F2, Y F1 | XY| L})
M2(
C1
n-L-1
)
k-L-1
G+
C2
pares poss.
Obs: L < |X Y|
Ago/2003
true

true
falsos neg. Aprox
por retirada
Y1
.....
Y
..... Yk
G+
false
X1
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
.....
X
.....
TECMF
Xj
Aprox(C1) = CC(F1)
Y1 ..... Y ..... Yk
G+
true
Aprox
X1
G+
.....
X
.....
Xj
true
Aprox(C2) = CC(F2)
Aprox(C1 AND C2)
CC({XY/X F2, Y F1})
Y1
.....
Y
CC({XY/X F2, Y F1 | XY| L})
..... Yk
G+
Y1
true
X1
Ago/2003
.....
X
.....
Xj
.....
Y
..... Yk
G+
false
X1
.....
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
X
.....
Xj
TECMF
Lema III: Todo circuito aproximante ou é idêntico ao circuito “falso” ou
resulta em “verdadeiro” em pelo menos metade dos exemplos
negativos.
ObsI: A operação de aproximação de um AND pode deletar todos os pares.
ObsII: Se o circuito aproximante (ingênuo CC(X1,...,Xp)) aceita algum circuito
Algum Xi aceita os exemplos negativos (têm cliques)
Existem
| Zi |
2
k-1
L

2
k-1

L!
(L-2)! 2!
k-1
8
(n)!
= (n4 -2)! 2!  1/2
n -1
8
exemplos de circuitos k-1 colorações em um circuito de L vértices
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Colapso da hierarquia polinomial de complexidade
Definição: P/Poly é a classe de linguagens aceita por circuitos booleanos de
tamanho polinomial.
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Exemplo positivo de tamanho n
- Um grafo com (
possíveis
k
2
) arestas conectando k vértices de todas as formas
n
Obs: Existem ( k ) exemplos positivos
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Exemplo negativo de tamanho n
- Colorir os vértices com (k-1) cores diferentes e unir por uma aresta todos os
pares de nós que são coloridos com cores diferentes.
Obs: Existem (k-1)n exemplos negativos (contando isomorfismo)
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
A(PA = NPA)
A = { <T,w,1k> / w é aceita por T usando no máximo k células }
PA

NPA
L NPA  PA
T
w
wL
T’
(fácil)
 L
A: T’ w 1p’(|w|)
w0
p(|w|)
A T’’wn
w0
,1k
A T’’wn,1k
wn
wn
p’(|w|)
sim
sim
p(|w|)
Ago/2003
wn
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
1k
wsk
C( PC  NPC)
NPC  PC
- X um oráculo qualquer
- enumeração construtiva de PX : {T0, T1,....., Tn,........}, tal que,
- Para qualquer x e k, Tk(x) pára no máximo em |x|k + k
LX = {0n / x(x X e |x|=n}
Obs: LX  NPX
- Vamos definir C (um oráculo do tipo X) de forma a LC  PC
- Obs: |x|k + k < 2|x|
O quantidade de strings de tamanho |x| é maior que qualquer poli em |x|
- Qualquer Tk  PC , calculando Tk(w) pode submeter no máximo
|x|k + k strings de tamanho |x| ao oráculo C.
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Diagonalização em partes para definir C:
C(i) = {w / w C e |w| = i}
C(0) = {}
||W|| = max{|w| / w W }
Objetivo.
- Se TiC(i-1)(0i ) = “aceita” então C(i) = {}.
- Se TiC(i-1)(0i ) = “rejeita” então C(i) = {min{w / |w| > ||C(i-1)||i-1 + i-1 e
2|w| > |w|i + i }}
LC  PC ==> existe Ti tal que LC é aceita por Ti ==>
Se TiC(0i ) = “aceita” então 0i  C(i) = {}
Se TiC(0i ) = “rejeita” então 0i  C(i)  0i
LC  PC
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Pred(i,k) =true  j 0 j  i, w( |w| = i  steps(Tj,w)  k)
N(i) =  |alfabetoj|i
j=0,i
2
f(i) = 2
2
2 s-vezes
2
2
2
2 s-vezes
onde s  N(i) e Pred(i, 2
)
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Suponha Paraf  DTime(f(x/2))
Diagf (T) = se TParaf(T,T) = “sim” então “não” senão “sim” es
Diagf “roda” em tempo f(2n+1/2) = f(n)
Diagf (Diagf ) = “sim”

Diagf (Diagf ) = “não”

Ago/2003
TParaf(Diagf,Diagf) = “não”
Diagf não aceita sua descriçao em tempo f(n)
TParaf(Diagf,Diagf) = “sim”
Diagf aceita sua descriçao em tempo f(n)
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
C1 e C2 são construtivamente enumeráveis
 Tji (i=1,2) (j  N) tal que Tji decide Lji  Ci
Li Ci
Define-se G tal que G  P e :
j z  *
Fazendo
z  L i L ji e z  G
L = (L1  G)  (L2  Gc)
j z  * z  Li Lji e z  G
Ago/2003
j z  * z  L Lji e z  G
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Z1i,n = menor palavra z com |z| >= n e z  L1L1i
Z2i,n = menor palavra z com |z| >= n e z  L2L2i
Rk(n) = max{|Zi,n |} + 1
in
k
L1C1 ===> L1L1i para todo i
C1 fechada por var. finita ====> para todo j e nj existe z  L1L1j
R1 é total e computável
R é uma função de tempo construtível tal que R(n)  max(R1(n), R2(n)).
G = { x / R2n(0)  |x|  R2n+1(0) e n  0}
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
G  P
T = Máquina de Turing que conta o tempo de R.
T(x) pára em exatamente R(|x|) passos
Algoritmo - Executar |x| passos de T(10) verificando se
R(0) > |x| ==> R(0) > |x| > 0
Executar |x| passos de T(1R(0)) verificando se
R(R(0)) > |x| ==> R(R(0)) > |x| > R(0)
n
R(0)
T(1 )
Executar |x| passos de
verificando se
Rn(0) > |x| ==> Rn(0) > |x| > Rn-1(0)
até achar o intervalo e verificar se n é par ou impar
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Teorema: Se existe uma linguagem unária (L {1}*) NP-completa então
NP = P
Suponha L unária e NP-completa
Existe uma redução R polinomial, tal que, x  SAT, sss R(x)  L
Notação: t {0,1} * => A[t] = fórmula A avaliada parcialmente por t (ordem nas letras)
Árvore de avaliação do valor verdade de A
A
A[0] A[1]
A[00]
t .... f t
Ago/2003
A[01] A[10] A[11]
t .. f
n = |A|
f ... t t ... t
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Construção de um algoritmo poli para SAT
Algoritmo I
Verifica(A[t]) = Se |t| = n então Se A[t]{} então falso
senão verdadeiro (A[t] verd)
senão Verifica(A[t0]) or Verifica(A[t1])
Algoritmo II
Verifica(A[t]) = Se |t| = n então Se A[t]{} então falso
senão verdadeiro (A[t] verd)
senão Se Tabela(hash(t))=DEF então Tabela(hash(t))
senão Verifica(A[t0]) or Verifica(A[t1]);
Insere_Resultado_emTabela;
Propriedades desejáveis do hashing:
1- Ter domínio pequeno (poli)
2- Se hash(t)=hash(t’) então A[t]  Sat sse A[t’]  Sat
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
hash(t) = R(A[t])
TECMF
Estimativa de complexidade do Algoritmo II
1- Sendo C o número de chamadas recursivas então a complexidade é
O(C.p(n)).
2- Existe uma sequência de avaliações parciais : {t1,..., tk} tal que
- k  C/2n
- todas as chamadas associadas são recursivas
- nenhum ti e préfixo de nenhum tj (i distinto de j)
Conclusão: O valor máximo de k é p(n), então
p(n)  C/2n
Ago/2003
O(np2(n)) é uma cota para Algoritmo II
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Speedup Linear
|| símbolos
Máquina M
original
a b c b
|Q| estados
=> Seja m um inteiro (dependendo de  e de M)
m
m
Máquina M
a b c b
c a a c
|| + ||m símbolos
Ago/2003
ac......
muito mais que
|Q| estados
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF
Passos na simulação de M por M:
1- Copiar o string da fita de entrada nas n/m primeiras células da segunda fita
2- Simular cada m passos de M em 6 passos de M.
- 4 (E,D,D,E) para “ler símbolos” relevantes , armazena nos estados
- 2 (E,D ou D,E) para fazer as m substuições
a b c b c a a c c
m
b c
m
bc........
bcaacc....
.......abc
3 - (1) gasta n+2 passos e 2 gasta 6.f(n)/m , total = 6.f(n)/m + n+2
4 - Fazendo m = 6/ obtem-se o resultado
Ago/2003
Topicos em Teoria de Complexidade
Prof. Edward Hermann Haeusler
TECMF