PROBLEMAS INTRATABLES E INDECIDIBLES

PROBLEMAS INTRATABLES E INDECIDIBLES

Zamir Hamet Orozco Jurado

Universidad Tecnológica de Bolívar

Cartagena Colombia

zojurado@gmail.com

Resumen---Un problema computacional constituye una pregunta a ser respondida, teniendo generalmente varios parámetros, o variables libres, cuyos valores no se han especificado.

Abstract --- A computational problem is a question to be answered, usually taking several parameters, or free variables whose values are not specified.

I. INTRODUCCION

En el presente artículo describiré los conceptos de problemas computacionales enfocándome en los intratables e indecidibles los cuales derivan de las 2 principales categorías problemas decidibles y indecidibles, de estas categorías los primeros pueden ser tratables o intratables, mientras que los últimos podían ser indecidibles o altamente indecidibles.

II. CONTENIDO

Problemas Computacionales

En primera instancia podríamos clasificar a los problemas en:

• Computables (decidibles)

• No computables (no decidibles)

Los problemas decidibles [1] se clasifican según los recursos (espacio y/o tiempo) que consumen para ser resueltos usando siempre su mejor solución algorítmica conocida para la peor entrada posible. Indecidibles, por su parte, aplica a una fórmula que no pertenece a un determinado sistema formal y que su negación tampoco pertenece al mismo. Esta noción está relacionada con la incompletitud del sistema.

Un ejemplo clásico de un problema indecidible es el ya mencionado problema de Hilbert [3]:

Determinación de la solubilidad de una ecuación diofantica: dada una ecuación diofantica con un número arbitrario de incógnitas y con coeficientes enteros racionales: idear un proceso por el que se pueda determinar mediante un número finito de operaciones si la ecuación es soluble en enteros racionales.

Este es el tipo de problemas que se plantearon en el programa formalista de Hilbert, dicho en un lenguaje menos técnico: establecer para las teorías matemáticas procedimientos de tipo finito para decidir si una fórmula dada es

o no un teorema de la teoría [2], este es el problema de decisión de la teoría o

Entscheidungsproblem. Plantear este problema constituía el sueno de Leibniz de tener un calculus ratiocinator que decidiera sobre las verdades lógicas, mediante la reducción del razonamiento, al cálculo aritmético.

El problema indecidible de los mosaicos

El siguiente problema se basa en una tesela o baldosa, las cuales son estructuras geométricas cerradas como las de la figura 2.

Figura 2: Imagen de un ejemplo de tesela Wang y su configuración de color

La entrada al problema es un número finito de teselas T. Cada tesela de T tiene su descripción definida por sus cuatro colores en un orden. El problema se plantea como a continuación:

Dada cualquier superficie finita, de cualquier tamaño, ¿puede recubrirse usando teselas de los tipos de T, de forma que las teselas adyacentes tengan el mismo color en los lados que se tocan? Además, existen las restricciones de que las teselas no se pueden rotar ni re-flejar.

Nótese que hay un número ilimitado de baldosas de cada tipo, pero el número de tipos es finito.

Figura 3: Representación del problema de dominio de Wang en una superficie.

Problema de la parada y verificación

Con el ejemplo anterior podemos introducir otros dos problemas muy conocidos por su fuerte grado de indecibilidad: Problema de la parada: dado un programa (o algoritmo) A y un valor de entrada X ¿se puede construir un algoritmo para saber siempre si A pararía o no? Hasta el momento

...