FTC

Defina las métricas de complejidad computacional más utilizadas

Tiempo = cantidad de pasos ejecutados por una MT
Espacio = cantidad de celdas ocupadas por una MT

Cuándo se dice que una MT M tarda tiempo T(n)

Sii a partir de toda entrada w, M hace a lo sumo T(n) pasos

Cuándo un lenguaje L pertenece a TIME(T(n))

Sii existe una MT M que lo decide en tiempo O(T(n))

Cuándo un lenguaje pertenece a la clase P

Cuando el lenguaje es aceptado por una MT en tiempo poly(n). Problema decidible en tiempo poly(n)

¿Qué dice la Tesis Fuerte de Church-Turing?

Si L es decidible en tiempo poly(n) por un modelo computacional físicamente realizable, también es decidible en tiempo poly(n) por una MT.

¿Cuándo un lenguaje pertenece a NP?

Si cuenta con una MT M que en poly(|w|) pasos puede verificar si w pertenece a L, con la ayuda de otra cadena.

¿Qué es una reducción polinomial?

Una reducción de L1 a L2 de tiempo polinomial.

¿Cuándo un lenguaje pertenece a NPC?

1. L ∈ NP

2. Todo Li ∈ NP cumple Li <=p L (L es NP difícil)

   Todos los lenguajes de NP se reducen polinomialmente al lenguaje L.

¿Cómo se encuentran lenguajes NP-completos?

1. Probar que L pertenece a NP

2. Construir una reducción polinomial f de SAT a L

¿Qué lenguajes pertenecen a NPI?

Los que no cuentan con una MT de tiempo polinomial que los decida, y no cuentan con una reducción polinomial desde un lenguaje NP-completo

¿Cuándo una MT M ocupa espacio S(n)?

Sii al ejecutarse desde toda entrada w, M ocupa a lo sumo S(n) celdas en cualquier cinta distinta de la de entrada.

¿Por qué la cinta de entrada es de sólo lectura y no se considera en la medición del espacio?

Para poder tener un espacio menor que lineal, es decir menor que O(n).

¿Cuándo un lenguaje pertenece a PSPACE?

Cuando es aceptado por una MT en un espacio poly(n)

¿Qué es una MT probabilistica?

Una MT que en cada paso elige aleatoriamente una entre dos continuaciones, cada una con probabilidad 1/2.

¿Qué es un alfabeto?

Un conjunto finito de símbolos Ʃ = {a, b, c}

¿Qué es un lenguaje?

Es un conjunto de cadenas finitas de símbolos de Ʃ. L = {aaa, b, ababab, ccb}

¿Qué es una máquina de turing?

Una modelización muy simple de una computadora, utilizada para estudiar la computabilidad y la complejidad computacional de los problemas

¿Qué dice la tesis de church turing?

Todo dispositivo computacional físicamente realizable puede ser simulado por una MT

¿Cuándo dos MT son equivalentes?

Cuando aceptan el mismo lenguaje (resuelven el mismo problema)

¿Cuándo dos modelos de MT son equivalentes?

Si dada una MT de un modelo existe una MT equivalente de otro.

¿Cuándo un lenguaje pertenece a R?

Cuando tiene una MT que lo acepta y para siempre

¿Cuándo un lenguaje pertenece a RE?

Cuando tiene una MT que lo acepta pero no siempre para

¿Cuándo un lenguaje pertenece a L?

Cuando no tiene MT que lo acepte

¿Que propiedades cumple R?

1. Si L ∈ R entonces L^c ∈ R

2. Si L1 y L2 ∈ R, entonces la intersección también

3. Lo mismo para la unión

¿Cuándo un lenguaje pertenece a CO-RE?

Cuando su complemento está en RE

¿Qué es una máquina de Turing universal?

Una máquina de turing capaz de ejecutar cualquier otra

¿Qué es una reducción?

Una función total computable (definida para todas las cadenas de Ʃ* y computable por una MT M) que para toda cadena w:

Si w ∈ L1, entonces f(w) ∈ L2

Si w ∉ L1, entonces f(w) ∉ L2

¿Qué propiedades tienen las reducciones?

Si L1 ≤ L2, entonces L2 ∈ R → L1 ∈ R

Si L1 ≤ L2, entonces L1 ∉ R → L2 ∉ R

Lo mismo para RE u otros.

Además reflexividad, transitividad y L1 ≤ L2 sii L1^c ≤ L2^c