MAC 722 Introdução à Teoria da Complexidade Computacional
Horário: segundas-feiras das 16:00 às 18:00 e quartas-feiras das 14:00
às 16:00.
Local: sala 267 do bloco A.
Conteúdo das Aulas durante o mês de maio
- Aula 16 (4 de maio)
- Entrega da terceira lista de exercícios.
- Teorema (Immerman-Szelepcényi)
Dado um grafo G e um vértice x, o número de vértices
atingíveis a partir de x em G pode ser computado por uma
máquina de Turing não-determinística em espaço log n.
- Corolário Se f(n) >= log n é uma função fácil,
então NSPACE(f(n))=co-NSPACE(f(n)).
- Definição Uma linguagem L1 reduz a uma linguagem L2
se exsite uma função R de strings em strings, computável por uma
máquina de Turing determinística em espaço O(log n) tal que
x \in L1 se e somente se R(x) \in L2.
(R é chamada de uma redução de L1 em L2.)
- Proposição Se f é uma função computada por uma
máquina de Turing determinística M em espaço O(log n) então a
máquina M alimentada com uma entrada x de tamanho n pára depois
de um número polinomial de passos. (Ou seja a Classe SPACE(log
n) está contido em P---não se sabe se SPACE(log n) está
propriamente contida em P.)
- Comentários sobre: polynomial transformations,
Karp-reducibility, Turing- ou Cook-reducibility...
- Aula 17 (6 de maio)
- Entrega da quarta lista de exercícios.
- Exemplo de redução O problema Caminho Hamiltoniano
pode ser reduzido ao problema SAT.
- Definições de fórmula, função e circuito booleanos.
- Notação Denotamos por $X(C)$ o conjunto das
variáveis de um circuito $C$. Denotamos por $T(C)$ o valor
de um circuito booleano resultante da atribuição $T$.
- Problema Circuit SAT
Dado: um circuito $C$
Pergunta: existe atribuição $T$ tal que $T(C)=true$?
- Problema Circuit Value
Dado: um circuito $C$ com $X(C)$ vazio
Pergunta: qual o valor de $C$?
- Exemplo de redução O problema $st$-caminho pode
ser reduzido ao problema Circuit Value.
- Aula 18 (11 de maio)
- Exemplo de redução O problema Circuito SAT pode
ser reduzido ao problema SAT. Além disso, cada cláusula da
instância de SAT tem no máximo $3$ literais.
- Proposição Se $R$ é uma redução de $L_{1}$ para
$L_{2}$ e $R'$ uma redução de $L_{2}$ para $L_{3}$, então
$R' \circ R$ é uma redução de $L_{1}$ para $L_{3}$.
- Definição de Completude Seja $\mathcal{C}$ uma
classe de complexidade e seja $L$ uma linguagem de
$\mathcal{C}$. Diremos que $L$ é $\mathcal{C}$-completa se
toda linguagem de $\mathcal{C}$ pode ser reduzida a $L$.
- Definição Dizemos que $\mathcal{C}$ é fechada sob
reduções quando $L'$ ser redutível a $L \in \mathcal{C}$
implicar que $L' \in \mathcal{C}$
- Proposição L, NL, P, NP, coNP, PSPACE e EXP são
todas fechadas.
- Proposição Se duas classes $\mathcal{C}$ e
$\mathcal{C'}$ são ambas fechadas e existe uma linguagem
$L$ que é completa em $\mathcal{C}$ e pertence a
$\mathcal{C'}$, então $\mathcal{C} \subseteq \mathcal{C'}$
- Aula 19 (13 de maio)
- Teorema Circuit Value é P-completo.
- Aula 20 (18 de maio)
- Teorema SAT é NP-completo.
- Proposição 3-SAT é NP-completo.
- Proposição 3-SAT é NP-completo, mesmo se nas
cláusulas cada variável aparece no máximo três vezes e
cada literal no máximo duas vezes.
- Proposição 2-SAT pertence a P.
- Definição Uma relação $R \subseteq \sigma^{*}
\times \sigma^{*}$ é polinomialmente decidível se existe
uma máquina de Turing determinística decidindo
$\{x;y|(x,y) \in R\}$ em tempo polinomial.
- Definição Uma relação $R$ é polinomialmente
balanceada se $(x,y) \in R$ implicar que $|y| \leq
p(|x|)$, onde $p$ é um polinômio que depende apenas de
$R$.
- Proposição $L \in NP$ se e somente se existe uma
relação $R$ polinomialmente decidível e balanceada tal que
$L=\{x|(x,y) \in R \mbox{ para algum } y\}$
- Aula 21 (20 de maio)
- Teorema Cada um dos problemas abaixo
é NP-completo.
- Problema MAX-2SAT (versão decisão)
Dado: um conjunto $\phi$ de cláusulas com no máximo
$2$ literais por cláusula e um inteiro $k$.
Pergunta: existe atribuição às variáveis de $\phi$
que satisfaçam pelo menos $k$ de suas cláusulas?
- Problema NAE 3SAT (Not-All-Equal 3SAT)
Dado: um conjunto $\phi$ de cláusulas com no máximo
$3$ literais por cláusula.
Pergunta: existe atribuição $T$ às variáveis de $\phi$
tal que cada cláusula contém literais $l$ e $l'$ tais que
$T(l) \neq T(l')$?
- Problema Independent Set
Dado: um grafo $G$ e um inteiro $k$.
Pergunta: existe em $G$ um conjunto de vértices
independentes de cardinalidade pelo menos $k$?
- Problema Clique
Dado: um grafo $G$ e um inteiro $k$.
Pergunta: existe em $G$ um clique de cardinalidade
pelo menos $k$?
- Problema Vertex-Cover
Dado: um grafo $G$ e um inteiro $k$.
Pergunta: existe em $G$ um conjunto de vértices que
cobre todas as arestas e tem cardinalidade no máximo $k$?
- Problema Caminho Hamiltoniano
Dado: um grafo $G$.
Pergunta: existe em $G$ um caminho hamiltoniano?
- Aula 22 (25 de maio)
- Teorema Cada um dos problemas abaixo
é NP-completo.
- Problema TSP
Dado: um conjunto $\{1,2,\ldots,m\}$ de cidades,
inteiros positivos $d(i,j)$ para cada $1 \leq i\neq j \leq
m$ e um inteiro $B$.
Pergunta: existe uma permutação $\pi$ tal que
$\sum_{i=1}^{m-1}d(\pi(i),\pi(i+1))+d(\pi(n),\pi(1)) \leq B$?
- Problema Tripartite Matching (3-Dimensional Matching)
Dado: $T \subseteq B\times G\times H$, onde $B$, $G$
e $H$ são disjuntos, cada um contendo $n$ elementos.
Pergunta: existe $T' \susbseteq T$ tal que $|T'|=n$
e nenhum elemento de $B$, $G$ ou $H$ ocorrem em mais do
que uma tripla?
- Problema Set Covering
Dado: um conjunto
$\mathcal{F}=\{S_{1},S_{2},\ldots,S_{n}\}$ de subconjuntos
de um conjunto finito $U$ e um inteiro $k$.
Pergunta: existem no máximo $k$ conjuntos em
$\mathcal{F}$ cuja união é $U$?
- Problema Set Packing
Dado: um conjunto
$\mathcal{F}=\{S_{1},S_{2},\ldots,S_{n}\}$ de subconjuntos
de um conjunto finito $U$ e um inteiro $k$.
Pergunta: existem $k$ conjuntos 2-a-2 disjuntos em
$\mathcal{F}$?
- Problema Exact Cober by 3-sets
Dado: um conjunto
$\mathcal{F}=\{S_{1},S_{2},\ldots,S_{n}\}$ de subconjuntos
de um conjunto $U$ de tamanho $3m$ com cada $|S_{i}|=3$.
Pergunta: existem $m$ conjuntos em $\matcal{F}$ que
têm $U$ como união?
- Problema Programação linear inteira
Versão 1
Dado: Matriz inteira $A$ e vetor inteiro $b$.
Pergunta: $Ax \geq b$ tem uma solução inteira?
Versão 2
Dado: Matriz inteira $A$, dois vetores inteiros
$b$ e $c$ e um inteiro $B$.
Pergunta: $Ax \geq b$ tem uma solução inteira
$x^{*}$ tal que $c^{T}x^{*} \leq B$?
- Problema Knapsack Problem
Dado: inteiros $v_{1}, v_{2},\ldots,v_{m}$ (valores)
inteiros positivos $w_{1}, w_{2},\ldots,w_{m}$ (pesos)
inteiro positivo $W$ (peso máximo)
inteiro $k$.
Pergunta: existe $S \subseteq \{1,2,\ldots,n$ tal
que $\sum_{i \in S}w_{i} \leq W$ e $\sum_{i \in S}v_{i} \geq k$?
- Proposição Knapsack pode ser resolvido em tempo
$O(nW)$ numa RAM sob custo unitário onde $n$ é o número de
ítens e $W$ o peso limite.
- Notação Seja $P$ um problema e $\mathcal{I}$ seu
conjunto de instâncias. Para $I \in \mathcal{I}$,
denotamos por $\sigma(I)$ o tamanho da instância $I$ e por
$MAX(I)$ a magnitude do maior númeor inteiro ocorrendo em
$I$. Se nenhum inteiro ocorre em $I$, então $MAX(I)=0$.
- Definição Um algoritmos pseudo polinomial
para $P$ é um algoritmo cuja complexidade em tempo é
limitada por um polinômio em $\sigma(I)$ e $MAX(I)$.
- Definição Seja $\matcal(I)_{f}=\{I \in
\matcal{I}|MAX(I)\leq f(\sigma(I))\}$, onde $f$ é uma
função dos inteiros nos inteiros. Seja $P_{f}$ o problema
$P$ restrito a $\mathcal(I)_{f}$. Dizemos que $P$ é
NP-completo "in the strong sense" ("strongly NP-complete")
se $P_{p}$ é NP-completo para algum polinômio $p$.
- Aula 23 (27 de maio)
- Definição Um programa RAM é fortemente
polinomial se:
- ele opera em tempo polinomial sob custo logarítmico
- o número de instruções RAM executadas pelo programa
independe da magnitude dos números da entrada
- Definição Problema de otimização:
- para cada instância $x$ existe um conjunto $F(x)$
de soluções viáveis
- para cada $s \in F(x)$ existe um inteiro positivo
$c(s)$
- $OPT(x)=\min_{s \in F(x)}c(s)$ (problema de
minimização) ou
- $OPT(x)=\max_{s \in F(x)}c(s)$ (problema de maximização)
- Definição Seja $M$ um algoritmo que, dada uma
instância de um problema de otimização $A$ retorna uma
solução $M(x) \in F(x)$. Dizemos que $M$ é um algoritmo de
aproximação $\epsilon$ se, para todo $x$, temos
$|OPT(x) - c(M(x))|/\max\{OPT(x),c(M(x))\} \leq \epsilon$.
- Proposição Existe um $1/2$ algoritmo de
aproximação polinomial para o problema Cobertura de
Vértices (versão otimização).
- Teorema Para cada $\epsilon > 0$ fixo existe uma
$\epsilon$-algoritmo de aproximação polinomial para
Kanpsack (versão otimização).
- Definição Um esquema de aproximação
polinomial para um problema de otimização $A$ é um
algoritmo que, para cada $\epsilon > 0$ e para qualquer
instância $x$ de $A$, retorma uma solução com erro
relativo $\epsilon$ em tempo limitado por um polinômio em
$|x|$ (o polinômio pode depender de $\epsilon$).
Quando a complexidade de tempo do
algoritmo de aproximação é um polinômio em $|x|$ e
$1/\epsilon$, dizemos que o esquema é fortemente
polinomial.
MAC 722's Home Page.
Last modified: Mon Aug 24 08:27:59 EST 1998