En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P. La razón es que de tenerse una solución polinómica para un problema NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico. Si se demostrase que un problema NP-completo, llamémoslo A, no se pudiese resolver en tiempo polinómico, el resto de los problemas NP-completos tampoco se podrían resolver en tiempo polinómico. Esto se debe a que si uno de los problemas NP-completos distintos de A, digamos X, se pudiese resolver en tiempo polinómico, entonces A se podría resolver en tiempo polinómico, por definición de NP-completo. Ahora, pueden existir problemas en NP y que no sean NP-completos para los cuales exista solución polinómica aún no existiendo solución para A.
Como ejemplo de un problema NP-completo encontramos el problema de la suma de subconjuntos que se puede enunciar como sigue: dado un conjunto S de enteros, ¿existe un subconjunto no vacío de S cuyos elementos sumen cero? Es fácil verificar si una respuesta es correcta, pero no se conoce mejor solución que explorar todos los 2n-1 subconjuntos posibles hasta encontrar uno que cumpla con la condición.
Un problema de decisión C es NP-completo si:
- C es un problema NP, y
- Todo problema de NP se puede transformar polinómicamente en C.
Se puede demostrar que C es NP demostrando que un candidato a solución de C puede ser verificado en tiempo polinómico.
Una transformación polinómica de L en C es un algoritmo determinista que transforma instancias de l ∈ L en instancias de c ∈ C, tales que la respuesta a c es positiva si y sólo si la respuesta a l lo es.
Como consecuencia de esta definición, de tenerse un algoritmo en P para C, se tendría una solución en P para todos los problemas de NP.
Esta definición fue propuesta por Stephen Cook en 1971. Al principio parecía sorprendente que existieran problemas NP-completos, pero Cook demostró (teorema de Cook) que el problema de satisfacibilidad booleana es NP-completo. Desde entonces se ha demostrado que miles de otros problemas pertenecen a esta clase, casi siempre por reducción a partir de otros problemas para los que ya se había demostrado su pertenencia a NP-completo; muchos de esos problemas aparecen en el libro de Garey and Johnson's de 1979 Computers and Intractability: A Guide to NP-completeness.
Un problema que satisface la segunda condición pertenece a la clase NP-hard independientemente de que satisfaga la primera.
LA COMPLEJIDAD, UN CONCEPTO OPERATIVO Y APLICABLE
Habíamos empezado hablando de la complejidad y hora es de volver a ella.
Se habrá advertido que cada una de las teorías o conjuntos teóricos examinados se ocupa de algun aspecto, inédito y de carácter cualitativo, de la realidad. Desde la perspectiva aquí adoptada, esto es importante por varias razones:
a) Estas teorías tienen un enorme valor epistemológico, pues abren vías de acceso a la realidad, que permiten aprehender ésta sin prescindir de su complejidad.
b) A la par, estas teorías ponen de manifiesto propiedades desconocidas de la realidad y con ello ofrecen un nuevo concepto de la complejidad. En este sentido, afirmar que la realidad es compleja significa, al menos, cuatro cosas: 1) Que la realidad es borrosa. 2) Que la realidad es catastrófica. 3) Que la realidad es fractal. Y 4) que la realidad es caótica.
c) Pero hay más: a la luz de estas teorías se nos aparece una realidad paradójica; una realidad que no es nítida pero tampoco es dual, que no es continua ni discontínua, ni es estable ni inestable, ni reiterativa ni innovadora, ni ordenada ni desordenada (sobre este último aspecto: Munné, en prensa b). Las propiedades de la complejidad subsumen estas alternativas, las cuales únicamente parecen tener pleno sentido en la realidad artificialmente producida por el ser humano (edificios, máquinas, utensilios, objetos producidos, etc.).
Así las cosas, hay que avanzar en el camino abierto por las teorías examinadas. Por ejemplo, un paso más en esa dirección se puede dar profundizando en las relaciones entre los aspectos de la complejidad puestos de manifiesto por dichas teorías u otras teorías de la complejidad que se vayan formulando. Algunas de estas relaciones ya son conocidas: La dimensión geométrica de carácter fraccionado o intermedio de los fractales parece ser indicadora de borrosidad. La teoría de las catástrofes describe la morfogénesis de la estabilidad y, en este aspecto, procesos no caóticos; con todo, es relacionable con la teoría del caos, porque este "se cuela" a través de la catástrofe. Además, la teoría de las catástrofes probablemente pueda ser reentendida a través de una teoría más general de las bifurcaciones e incluso de las oscilaciones. También los atractores extraños son fractaliformes: nunca se cortan o yuxtaponen debido a su determinismo y las trayectorias se "aprietan" más y más al reducir la escala de observación. Las turbulencias consisten, como los fractales, en irregularidades. Etc.
Otra cuestión es la de las relaciones entre las teorías de la complejidad, las cuales lógicamente no están exentas de discrepancias. Han originado ya polémicas importantes, por ejemplo, entre Mandelbrot y Thom, o entre Mandelbrot y Feigenbaum. Pero más allá de disputas puntuales, una cuestión que late en toda esta temática es la que opone la borrosidad, la estabilidad, la iteración, el equilibrio, etc. a los límites, los puntos críticos, los ciclos límite, las transiciones del espacio de fases, etc. A nivel epistemológico, esta cuestión no es nueva: cuando Louis de Broglie explicó en un libro, ya clásico en la filosofía de la ciencia, el enfrentamiento entre las interpretaciones corpuscular y ondulatoria del mundo físico puso un título a su obra que revela que los conceptos en lid siguen siendo los mismos: Continu et discontinu en physique moderne (1941).
¿ Cómo las aportaciones de las anteriores teorías, nacidas en las ciencias naturales, pueden ser aplicadas, en el pleno sentido empírico de la palabra, a las ciencias del comportamiento ?
La mejor manera de comprender cómo o en que sentido hay que entender esta aplicación es darse cuenta de que los constructos aportados desde el enfoque de la complejidad (como son los conceptos de fractal, conjunto difuso, torbellino, caos, atractor extraño, etc.) son altamente formalizables. Esto significa que pueden ser aplicados de un modo transdisciplinar, sin necesidad de acudir a metáforas ni analogías.
Es lo mismo que sucede con el concepto de feedback: usted puede aplicarlo, con pleno sentido, tanto a un motor como al cuerpo humano, desde a una galaxia a un movimiento social. Sin embargo a usted no se le ocurrirá que el cuerpo humano es un motor o que un motor es igual que el cuerpo humano, ni que una galaxia y un movimiento social son confundibles. Y sin aquel concepto muchos fenómenos o procesos, si es que pueden ser planteados, no pueden llegar a ser bien comprendidos. Piénsese tan sólo en la revelancia social de los procesos de autorregulación o autocontrol.
Como epistemologías, las teorías examinadas proporcionan un nuevo modo de aprehender la realidad y ayudan a una comprensión menos reductora de los procesos básicos del comportamiento y la realidad sociales.
Y esto no se queda en el análisis. Conlleva, también, al menos potencialmente, nuevas formas de tratamiento de la realidad. Ya se ha dicho que las teorías del caos han entrado en el campo del diagnóstico. Puede añadirse que están asomando al ámbito de la intervención. Una muestra de lo que esto puede significar la tenemos en las recientes investigaciones de Brenda Zimmerman (por ej., 1992) sobre la dirección estratégica, basada en el caos y en la fractalidad de las organizaciones.
