Upload
others
View
10
Download
0
Embed Size (px)
Citation preview
Complexidade Computacional na Geometria Algebrica
Thomas Michael Bartlett
UNICAMP
25 de novembro de 2016
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 1 / 25
Overview
1 Fundamentos da Complexidade ComputacionalDefinicao de Maquina de TuringMT Determinıstica e a classe PMT Nao-determinıstica e a classe NPProblema NP-Completo e teorema de CookNP-DifıcilOutras Classes de Complexidade
2 Exemplos NP-Completo na Algebra e Geometria3-SATTRAVELING SALESMANQUADRATIC DIOPHANTINE EQUATIONSALGEBRAIC EQUATIONS OVER GF[2]DECODING LINEAR CODESGROBNER BASIS
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 2 / 25
Definicao de Maquina de Turing - 1
Uma Maquina de Turing e um par de fita infinita e um cabecote comcontrole de estados finitos:
b b 0 00 b1 1
read-writehead
qi
... ...
0-1-2 1 2 3 4 5
Figura : Equipamentos da Maquina de Turing
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 3 / 25
Definicao de Maquina de Turing - 2
Def.: Um programa determinıstico para a MT e a tupla M = (Γ,Q, δ)
Um conjunto finito Γ = {b, γ1, ..., γn} de sımbolos;
Um conjunto finito Q = {qY , qN , q0, q1, ..., qd} de estados
Uma funcao δ : (Q− {qY , qN})× Γ→ Q× Γ× {−1,+1}, chamadafuncao transicao;
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 4 / 25
Exemplo de programa - 1
Seja o programa que reconhece se os dois sımbolos mais a direita sao 0:
Γ = {b, 0, 1};Q = {qY , qN , q0, q1, q2, q3};δ a seguir
q 0 1 b
q0 (q0, 1,+1) (q0, 1,+1) (q1, 1,−1)q1 (q2, b,−1) (q3, b,−1) (qN , b,−1)q2 (qY , b,−1) (qN , b,−1) (qN , b,−1)q3 (qN , b,−1) (qN , b,−1) (qN , b,−1)
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 5 / 25
Exemplo de programa - 2
read-writehead
b b 0 00 b1 1... ...q0:
b b 0 00 b1 1... ...q0:
b b 0 00 b1 1... ...q0:
b b 0 00 b1 1... ...q0:
b b 0 00 b1 1... ...q0:read-write
head
b b 0 00 b1 1... ...q0:read-write
head
b b 0 00 b1 1... ...
read-writehead
b b 0 b0 b1 1... ...
read-writehead
b b 0 bb b1 1... ...
read-writehead
read-writehead
read-writehead
read-writehead
q1:
q2:
qY:
Figura : Execucao do programa exemplo
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 6 / 25
Problemas de decisao - 1
Def.: Dizemos que um programa M aceita x ∈ Γ∗ se o programa terminaem qY quando o input e x . E dizemos que a linguagem LM reconhecidapelo programa M e
LM = {x ∈ Γ∗ : M aceita x}
Exemplo:
LM = {x ∈ {0, 1}∗ : os dois simbolos mais a direita de x sao 0}
Def.: Seja um problema de decisao Π numa codificacao e e uma instanciaI, a sua linguagem associada e
L[Π, e] = {x ∈ Γ∗ : Γ e o alfabeto de e e
x e uma codificacao em e de uma instancia I}
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 7 / 25
Problemas de decisao - 2
Exemplo: Numa codificacao binaria Γ = {b, 0, 1}:
Instancia: Um numero inteiro positivo NQuestao: Existe um numero m tal que N = 4m?
L[Π, e] = {N ∈ Γ∗ : existe m ∈ Γ∗ tal que N = 4m}
Def.: Dizemos que o programa M resolve um problema de decisao Π numacodificacao e se LM = L[Π, e].
Exemplo: No exemplos acima temos que LM = L[Π, e].
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 8 / 25
MT Determinıstica e a classe P
Def.: Seja um programa determinıstico M, sua funcao complexidadetemporal TM(n) e definida por :
TM(n) = max {m : existe um x ∈ Γ∗ , com |x | = n, tal que
M termina depois de m iteracoes de δ}
Exemplo: A funcao complexidade temporal de M e TM(n) = n + 2.
Def.: M e um programa determinıstico de tempo polinomial (PDTP) seexiste um polinomio p tal que TM(n) ≤ p(n),∀n ≥ 0.Def.: A classe de linguagens determinısticas de tempo polinomial P e
P = {L : existe um PDTP M tal que LM = L} .
Exemplo: [Π, e] ∈ P.
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 9 / 25
MT Nao-determinıstica e a classe NP - 1
Def.: Um programa nao-determinıstico (PND) e uma tupla M = (Γ,Q, δ),onde δ e uma relacao, δ ⊂ ((Q− {qY , qN})× Γ)× (Q× Γ× {−1,+1}).
Em um programa nao determinıstico e possıvel, testar todas as possıveissolucoes S de modo a testar a validade de questao com a instancia I ∈ Γ∗.
Def.: Seja um PND M, sua funcao complexidade temporal TM(n) edefinida por :
TM(n) = max {{1} ∪ {m : existe um x ∈ LM , com |x | = n, tal que
M termina depois de m iteracoes de δ}}
Nota.: A complexidade temporal de um PND M e, dado um input comtamanho n, determinar em quanto tempo uma solucao e verificada.
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 10 / 25
MT Nao-determinıstica e a classe NP - 2
Def.: M e um programa nao-determinıstico de tempo polinomial(PNDTP) se existe um polinomio p tal que TM(n) ≤ p(n), ∀n ≥ 0.Def.: A classe de linguagens nao-determinısticas de tempo polinomial NPe
NP = {L : existe um PNDTP M tal que LM = L} .
Exemplo: P ⊂ NPTeo.: Se Π ∈ NP, entao existe um polinomio p tal que Π e resolvido porum programa determinıstico em tempo O(2p(n)).
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 11 / 25
MT Nao-determinıstica e a classe NP - 3
Com
ple
xit
y
P ≠ NP P = NP
NP-Hard
NP-Complete
P
NP
NP-Hard
P = NP =NP-Complete
Figura : Dependencias de classes
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 12 / 25
Problema NP-Completo e teorema de Cook - 1
Pergunta: P 6= NP ?
Def.: Uma linguagem L1 ⊂ Γ∗1 transforma polinomialmente em L2 ⊂ Γ∗2(L1 ∝ L2), se existe uma funcao f : Γ∗1 → Γ∗2 tal que:
existe um PDTP que computa f ;
∀x ∈ Γ∗1, x ∈ L1 ⇐⇒ x ∈ L2.
Lema: Se L1 ∝ L2, entao L2 ∈ P implica L1 ∈ P.Lema: Se L1 ∝ L2 e L2 ∝ L3, entao L1 ∝ L3
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 13 / 25
Problema NP-Completo e teorema de Cook - 2
Def.: Dizemos que L ∈ NP e NP-Completo se L′ ∈ NP⇒ L′ ∝ L.
Observacao: Seja L ∈ NP NP-Completo, se L ∈ P entao NP ⊂ P.
Lema: Sejam L1, L2 ∈ NP, L1 e NP-Completo e L1 ∝ L2 entao L2 eNP-Completo.Observacao: Para provar que uma linguagem L e NP-Completa, deve-se:
provar que L ∈ NP;
provar que uma linguagem L0 conhecidamente NP-Completatransforma polinomialmente para L, L0 ∝ L.
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 14 / 25
Problema NP-Completo e teorema de Cook - 3
O primeiro problema NP-Completo historicamente e o seguinte: SejaU = {u1, u2, ..., um} um conjunto de variaveis booleanas e uma valoracaode verdade t : U → {V ,F}. Uma formula booleana f pertencente aAlgebra de Boole e satisfazıvel se existe t tal que t(f ) = V .
Problema de satisfazibilidade booleana (SAT):Instancia: U um conjunto de variaveis booleanas e f uma formulabooleana;Questao: Existe uma valoracao t tal que t(f ) = V ?
Teo.: SAT e NP-Completo.
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 15 / 25
NP-Difıcil
Def.: Um problema L e dito NP-Difıcil se L′ ∈ NP entao L′ ∝ L.
Nota: NP-Completo ⇒ NP-Difıcil, mas nao vale a volta.
Exemplo: Em breve...
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 16 / 25
Outras Classes de Complexidade
P ⊂ NP ⊂ PSPACE ⊂ EXPTIME ⊂ NEXPTIME ⊂ EXPSPACE
Ha um zoologico de classes de complexidade! (https://complexityzoo.uwaterloo.ca/Complexity_Zoo )
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 17 / 25
3-SAT
Def.: Uma formula 3-booleana e f = c1 ∧ c2 ∧ · · · ∧ cm com|ci | = Numero de variaveis emci = 3.
Problema de 3-satisfazibilidade booleana (3-SAT)Instancia: U um conjunto de variaveis booleanas e f uma formula3-booleana;Questao: Existe uma valoracao t tal que t(f ) = V ?
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 18 / 25
TRAVELING SALESMAN
Problema de caixeiro viajante:Instancia: C = {c1, c2, ..., cm} cidades e uma distancia d(ci , cj) ∈ Z+ euma cota B ∈ Z+;Questao: Existe um tour T = (cπ(1), cπ(2), ..., cπ(m)) tal que
m∑i=1
d(cπ(i), cπ(i+1)) + d(cπ(m), cπ(1)) ≤ B ?
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 19 / 25
QUADRATIC DIOPHANTINE EQUATIONS
Equacao Quadratica Diofantina:Instancia: Sejam a, b, c ∈ Z+ ;Questao: Existe x , y ∈ Z+ tal que ax2 + by = c ?
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 20 / 25
ALGEBRAIC EQUATIONS OVER GF[2]
Equacao Algebrica em F2:Instancia:Sejam {Pi (x1, x2, ..., xn) : 1 ≤ i ≤ m} polinomios em F2 ;Questao: Existe u1, u2, ..., un ∈ {0, 1} tal que Pi (u1, u2, ..., un) = 0, ∀i ?
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 21 / 25
DECODING LINEAR CODES
Decodificacao de Codigos Lineares:Instancia: H uma matriz m × n em F2, s ∈ Fm
2 e t ∈ Z+ ;Questao: Existe um x ∈ Fn
2 tal que xHT = s com wt(x) ≤ t?
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 22 / 25
GROBNER BASIS
Sejam f0, f1, ..., fm ∈ K [x1, ..., xn], decidir se f0 ∈ 〈f1, ..., fm〉 eEXPSPACE-Completo;
Sejam f1, ..., fm ∈ K [x1, ..., xn] tal que o conjunto solucao e0-dimensional, entao calcular sua base de Grobner e PSPACE;
Se f1, ..., fm sao homogeneos entao calcular sua base de Grobner e NP.
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 23 / 25
References
Bardet, Magali. ”On the complexity of a Grobner basis algorithm.”AlgorithmsSeminar, 2002–2004. 2005.
Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: AGuide to the Theory of Np-Completeness. W. H. Freeman & Co., New York, NY,USA.
Pellikaan,Ruud. Coding Theory- MasterMath 2MMC30 Slides.(www.win.tue.nl/ ruudp/courses/2MMC30/week13-2.coding-theory.pdf)
Thomas Michael Bartlett (UNICAMP) Complexidade na Geometria 25 de novembro de 2016 24 / 25