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

...