Problemas, problemas,problemas

I've got 99 problems and 3-SAT reduces to all of them..—Reddit

Ivan Meza

ReducciónUn problema se reduce a , A B A ≤ B

Función de reducciónUna función

se reduce a si si y sólo si Sí entonces Sí entonces

f(w)A B w ∈ A f(w) ∈ B

w ∈ A f(w) ∈ Bw ∉ A f(w) ∉ B

Pequeño problemaConsiderar y reducir a LD 0∗1∗

Sí entonces Sí entonces

w ∈ LD f(w) = 01w ∉ LD f(w) = 10

¿Entonces reducimos a regular?LD

tiene que ser computablef

Reducción

Verdadero

Falso

W calcular f f(w) Máquina B

R

Máquina RCon la entrada w

Calcular Correr en Si acepta , entonces aceptar Si rechaza , entonces rechazar

f(w)MB f(w)

MB f(w) wMB f(w) w

Notación , es reducible a A B≤M A B

PropiedadesSi A, entonces Si A,B y C entonces y entonces

A ≤ BA ≤ B B ≤ C A ≤ C

Informalemente, A no es más difícil que B

Reducciones famosas

donde donde

donde donde

HALT ≤ Lu

≤ HALTLu

HALT ≤ DECIDER {m|is a decider}≤ ONESLu {m|m acepta w con forma  }1n

≤ ONLY ONESLd {m|L(m) ⊆ }1∗

≤Ld ONLY ONES¯ ¯¯̄¯̄¯̄ ¯̄¯̄¯̄¯̄ ¯̄¯̄¯̄ ¯̄¯̄¯̄¯̄ {m|L(m) ⊈ }1∗

OpcionesSi A B≤M

Si es decidible, entonces lo esSi es computable, entonces lo esSi es indecidible, entonces lo esSi es no es computable (no RE), entonces lo es

B AB AA BA B

Dónde quedan en la jerarquíaextendida

donde donde

donde donde

HALT ≤ Lu

≤ HALTLu

HALT ≤ DECIDER {m|is a decider}≤ ONESLu {m|m acepta w con forma  }1n

≤ ONLY ONESLd {m|L(m) ⊆ }1∗

≤Lu ONLY ONES¯ ¯¯̄¯̄¯̄ ¯̄¯̄¯̄¯̄ ¯̄¯̄¯̄ ¯̄¯̄¯̄¯̄ {m|L(m) ⊈ }1∗

El poder de tener la respuesta si me dan una respuesta válida , es fácil de checar si me dan una inválida , no es tan fácil de checar

(loop) si me dan una respuesta inválida , es fácil

de checar si me dan una respuesta válida , no es fácil

de checar (loop)

ONES m, 1n

ONES m, 1n

ONLY ONES¯ ¯¯̄¯̄¯̄ ¯̄¯̄¯̄¯̄ ¯̄¯̄¯̄ ¯̄¯̄¯̄¯̄

m, ≠ 1n

ONLY ONES¯ ¯¯̄¯̄¯̄ ¯̄¯̄¯̄¯̄ ¯̄¯̄¯̄ ¯̄¯̄¯̄¯̄

m, 1n

RE y co-RERE es el conjunto de lenguajes reconocidos por una máquinade Turing

Problemas para los cuales veri�camos una respuesta correcta

co-RE es el conjunto de lenguajes cuyos complementso sonreconocidos por una máquina de Turing

Problemas para los cuales veri�camos una respuestaincorrecta

RE y co-RESi y , entonces Si y , entonces Si y , entonces Si y , entonces

L ∈ RE ∈ REL¯ ¯¯̄

L ∈ Rec

L ∈ RE ∈ coREL¯ ¯¯̄

L ∈ RecL ∉ R L ∈ RE L ∉ co − REL ∉ R L ∈ co − RE L ∉ RE

¿Qué sabemos de este lenguaje?

REGULAR = {[M]|L(M) es regular}

REGULARLD ≤M

REGULAR es no RE, pero

REGULARLD¯ ¯¯̄¯̄¯ ≤M

y afuera de los límites de locomputableREGULAR REGULAR

¯ ¯¯̄¯̄ ¯̄¯̄¯̄¯̄¯̄¯̄¯̄¯̄¯̄¯̄

¿Otro afuera?

E = {[ , ]|L( ) = L( )}QTM M1 M2 M1 M2

Lenguaje Gramática Máquina Ejemplo

Másalla/No RE

-- --

co-RE/NoRE

-- --

Tipo 0 ( )

MáquinadeTuring,APDo, AC

Tipo 1 ( )

Autómatalineal confronteras

Tipo 2 ( )

Autómatade pila

Tipo 3 ( )

Autómatafinito

REGULAR, REGULAR¯̄¯̄¯̄¯̄¯̄ ¯̄¯̄¯̄¯̄¯̄¯̄¯̄¯

, , , ONLY OLu¯ ¯¯̄¯̄

LD ONES¯ ¯¯̄¯̄¯̄¯̄ ¯̄¯̄¯

/LRE LRec

α → β, , ONES,Lu LD

¯ ¯¯̄¯̄¯ONLY O¯̄¯̄¯̄¯̄¯̄ ¯̄¯̄¯̄¯̄

LDC

αV β → αγβww, anbncn

LLC

V → αw ,wr anbn

Lreg

V → aA|ϵw, a∗

( ) finitoV → aA|ϵ

Resumen: Church-Turing tesisRec: problemas que pueden ser calculados por una computadoraRE: problemas donde respuestas pueden ser verificados por unacomputadoraco-RE: problemas donde respuestas pueden ser refutadas por unacomputadora

Fijandonos en los decidables¿Es posible resolver un problema eficientemente?

E�ciencia se mide en número de pasos/tiempo

Tipos de complejidadesContante Log log Logarítmica Raiz cuadrática Polinómica Polinómica Log Polinómica cuadrada Exponencial log Exponencial Factorial

O(1)O(log(n)log(n))

O(log(n))O( )n√

O(n)O(nlog(n))

O( )n2

O( )2log(n)

O( )2n

O(n!)

Tesis de Cobham-EdmondsUn lenguaje puede ser resuelto e�cientemente si se decideen tiempo polinómico

L

Clase de PTodos los problemas que se pueden resolver en en tiempopolinomial

EjemplosReconocer de un AF, AFND y AFND-Reconocer de un APDReconocer de un AP (!Compiladores!)¿Dado un grafo y dos nodos, estos se conectan?¿Dado un número es primo?Etc, ...

w ϵww

n

Clase de NPTodos los problemas que se pueden resolver en en tiempopolinomial por una MTND

NP es No determinístico en tiempo polinomial

Máquinas de TuringEs una tupla (Q, Σ, Γ, , B, A, δ)q0

conjunto finito de estados alfabeto de cadenas reconocidas alfabeto de cinta, estado inicial Símbolo de espacio en blanco pero estados finales

función de transición

QΣΓ Σ ⊂ Γq0B B ∈ Γ B ∉ ΣAδ Q × Γ → Q × Γ × {der, izq}

Máquinas de Turing nodeterminísticaEs una tupla (Q, Σ, Γ, , B, A, δ)q0

conjunto finito de estados alfabeto de cadenas reconocidas alfabeto de cinta, estado inicial Símbolo de espacio en blanco pero estados finales

función de transición

QΣΓ Σ ⊂ Γq0B B ∈ Γ B ∉ ΣAδ Q × Γ → {Q × Γ × {der, izq}}

Uso el no determinismo para adivinar respuestas

Uso el determinismo para veri�car la respuesta

Problemas fáciles de veri�car

Ejemplos de NPSodukoEl problema del agente de viajeUn grafo puede ser coloreado por coloresDeterminar la mejor forma de asignar trabajos a trabajadores

k

La pregunta más importante encomputación¿ ? o ¿ ?P = NP P ≠ NP

El cuarto problema de los problemas de Millenium

Solucción vale un millón de dolares

Descrito en 1971

NP-hardInformalmente, son los problemas que son tan difíciles comoel más difícil en NP

Formalmente, son los problemas que son tan difíciles como elmás difícil en NP

NP-complete

Intercección NP y NP-hard

Ejemplos

Satisfacción Lógica ProposicionalDe un conjunto de números podemos encontrar un conjunto quesume zero

Ejemplos

NP-completeHalting problem

Si y , entonces L ∈ NP-complete L ∈ P P = NP

¿Como resolvemos estos problemas?

AproximaciónAleatoriidadUso de restriccionesParametrizaciónHeurísticas

Para mayor información visitar el zoológico aquí

ivanvladimir@gmail.com ivanvladimir.github.io ivanvladimir

Problemas, problemas, problemas by is licensedunder a

. Creado a partir de la obra en

.

Ivan V. Meza RuizCreative Commons Reconocimiento 4.0 Internacional

License

http://turing.iimas.unam.mx/~ivanvladimir/slides/lfya/np_p.html