clasificacion de problemas

UNIVERSIDAD NACIONAL DE SANTIAGO DEL ESTERO
Facultad de Ciencias Exactas y Tecnologías
Licenciatura en Sistemas de Información

2009

CLASIFICACIÓN DE
PROBLEMAS

1

CLASES DE PROBLEMAS
Uno de los resultados fundamentales de Gödel, Turing y otros lógicos y
matemáticos fue el de establecer la división de todos los problemas matemáticos

PROGRAMACIÓN II

imaginables en dos clases:los demostrablemente irresolubles

los resolubles que admiten un algoritmo para su solución
Ciertos casos particulares de los primeros son posibles de resolver, la cuestión
importante es que nunca podrá hallarse un método general de resolución para
ellos.
Los demás problemas pueden resolverse por medio de algoritmos.

GEB

3

CLASES DE PROBLEMAS

PROGRAMACIÓN II

DEMOSTRABLEMENTEIRRESOLUBLES

CLASES

Problema de la detención de la MT
Décimo Problema de Hilbert

DEMOSTRABLEMENTE
DIFÍCILES
(algoritmos ineficientes)
RESOLUBLES
Tienen algoritmos
eficientes o aún
no se ha
demostrado su
inexistencia

CLASE P
Deterministicamente
Polinómicos
CLASE NP
No deterministicamente
Polinómicos
CLASE NP COMPLETA
CLASE CO NP
Complementarios de los NP

GEB

42

CLASES DE PROBLEMAS - GRÁFICO
PROBLEMAS DEMOSTRABLEMENTE IRRESOLUBLES
Problema de la detención de la MT
Décimo problema de Hilbert

PROGRAMACIÓN II

PROBLEMAS DEMOSTRABLEMENTE DIFÍCILES

CLASE NP
Completa

Probl.
de los números
compuestos

CLASE co-NP

Problema de Hamilton
Problema SAT
Problema de la clique

CLASE P

Problema de
Euler

CLASE NP

GEB

5PROBLEMA DE LA DETENCIÓN DE LA MT
Ciertos problemas son tan difíciles que no existen algoritmos que los
resuelvan. Un programa para el que no existirá nunca un algoritmo que lo
resuelva es llamado irresoluble o no computable.
PROGRAMACIÓN II

El problema de parada para máquinas de Turing es el ejemplo de problema
irresoluble más conocido. Fue además el primer problema que se demostróformalmente que no tenía solución.
Sea M una máquina de Turing arbitraria con un alfabeto de entrada Σ.
Sea w ε Σ*. ¿Puede decidirse si la máquina M parará con la entrada w?

Solución
La respuesta a esta pregunta es negativa. No se puede determinar si una
máquina de Turing se detiene con una entrada arbitraria.
GEB

6

3

DÉCIMO PROBLEMA DE HILBERT

Hallar un algoritmo para determinar sitoda ecuación diofántica (es

PROGRAMACIÓN II

decir, del tipo P(u1, u2, ..., un) = 0 donde P es un polinomio con
coeficientes enteros) tiene o no soluciones enteras.

Fue demostrado recursivamente insoluble por Matiyasevich en 1971.
Por ejemplo: x2 + y2 - z2 = 0 tiene una solución x=3; y=4;z=5
6x18 - x + 3 = 0 no tiene solución ya que ∀ x: 6x18 > x-3

GEB

7

PROBLEMASDEMOSTRABLEMENTE DIFÍCILES
Comprendida entre ambos grupos se encuentra una tercera categoría
de problemas los demostrablemente difíciles que, en principio,
PROGRAMACIÓN II

siempre es posible resolver; para los cuales, solo se conocen
algoritmos ineficientes (y, por consiguiente, la mayoría de las veces,
impracticables).

Los matemáticos han podido demostrar que, para algunos de estos
difícilesproblemas, nunca podrán prepararse algoritmos eficientes.
Para muchos de los problemas importantes se tiene únicamente la
sospecha de que será imposible encontrar algoritmos eficientes.

GEB

8

4

CLASE P
La CLASE P está constituida por algoritmos de tiempo polinómico.
Para que un problema sea asignado a la clase P ningún caso particular
PROGRAMACIÓN II

del problema puede exigir parasu resolución un tiempo mayor que el
polinómico.

El método de solución es determinístico en el sentido de que
garantiza la existencia de una solución, y ello en un tiempo inferior al
de una cierta potencia fija del tamaño N del problema.

GEB

9

CLASE NP
CLASE NP significa “No determinísticamente polinómicos”.

PROGRAMACIÓN II

La CLASE NP incluye a todos los problemas de la...