Introducción

Quizás lo más importante y difícil de los problemas en investigación tiene que ver con la identificación o formulación de estos. Un problema, desde luego, no es una pregunta; la razón para ello es que un problema se concibe, una pregunta se formula; mejor (o peor) aún: una pregunta se responde, un problema se resuelve. Más exactamente, la formulación del problema más que un acto analítico es un proceso de la imaginación. Y sin embargo, quienes hablan (aún) de metodología de la investigación – horribile dictu –suelen empatar ambas y hasta confundir una con la otra, preferir aquello y olvidar a esta. Ocuparse de estas confusiones es sencillamente necio, en el contexto de este artículo.
Los hombres y mujeres de ciencia se caracterizan hoy porque no trabajan con base en "objetos" –y por derivación, tampoco con "temas", "campos" y demás–, sino, mucho mejor aún, a partir de problemas. Este constituye, con seguridad, el rasgo más fuerte de contraste entre la ciencia clásica y la ciencia de
punta contemporánea. Aquella trabaja (ba) con objetos y campos, esta se funda en problemas –de investigación, justamente–. Ahora bien, el trabajo con problema y la identificación de los mismos es algo que se dice muy fácilmente pero que es (extremadamente) difícil de lograrlo.
Trabajar con problemas constituye, sin duda alguna, uno de los rasgos que permiten identificar qué y cómo se está trabajando con ciencia de punta. Pues bien, la clase de problemas que quisiera destacar aquí son los de frontera. Un problema se dice que es de frontera cuando una sola ciencia o disciplina es incapaz de comprender el dilema de que se trata con el problema, y cuando, adicionalmente, es incapaz de resolverlo por sí misma. Necesita entonces del concurso de otras metodologías, otros lenguajes, otros enfoques y tradiciones. Surge así lo que clásicamente se llama "interdisciplinariedad". Pues bien, gracias a los problemas de frontera emergen ciencias de frontera. Con ellas, se avanza un paso importante en el abandono de la tradición disciplinar de la ciencia.
Con este texto me propongo demostrar el título de este trabajo, a saber: que los problemas P vs. NP constituyen el núcleo fundamental de la investigación científica. No existe ningún trabajo en esta línea. En verdad, la mayoría de los trabajos alrededor de los problemas P vs. NP giran, con buenas razones, en torno a problemas computacionales –la mayoría– y matemáticos. A fin de demostrar la tesis según la cual la investigación de punta actual en el mundo se funda en los problemas mencionados se impone primero una somera presentación de la estructura y la lógica de los problemas P vs. NP. Esta es la primera sección. Seguidamente, sitúo a esta clase de problemas en el contexto de la complejidad, la innovación y la investigación. Finalmente, extraigo algunas conclusiones.

1. Métodología

Luego de señalar el origen de los problemas P vs. NP se señala que forman parte de los problemas del milenio. A una presentación somera de la estructura del problema le sigue su delimitación. Así, señalando que habitualmente se lo considera, con buenas razones, en el marco de consideraciones matemáticas, computacionales y lógicas, se dirige la mirada hacia la complejidad y, más allá de ella, se fija en el contexto de la metodología de la investigación científica. Se destaca el estudio teórico del tema tratado y se destaca al final una parte de la bibliografía más relevante.

2. Origen y estructura lógica de los problemas  P vs. NPa

En el origen de los problemas P vs. NP se encuentra la lógica en general, y más exactamente, el conjunto de problemas relativos a la computación y la teoría de la información. El tema fue formulado (= descubierto) de manera independiente, pero simultáneamente, por tres investigadores: Cook (1971), Karp (1972) y Levin (1973). Es tal la envergadura del problema que ha sido identificado como uno de los problemas del milenio ( The millenium problems) por el Instituto Clay (Carlson, et al ., 2006; Delvin, K., 2002).
Se impone una primera observación importante de orden teórico. El marco amplio de los problemas P vs. NP es la lógica en general. Pero la motivación particular es la teoría de la información y más exactamente la teoría de la computación. En rigor, se trata de los problemas lógicos y matemáticos de la computación. À la lettre lo que motiva a los problemas que aquí interesan son temas y problemas de
análisis combinatorios. Pues bien, tal es exactamente la razón por la que el Instituto Clay incluyó a estos problemas entre los más importantes de nuestra época. Así, la lógica y la matemática, la teoría de la información y los problemas relativos a la computación constituyen una sola unidad. Esta unidad es la que da lugar precisamente a la columna vertebral de las ciencias de la complejidad, o también, del estudio de los fenómenos, comportamientos y sistemas caracterizados por complejidad creciente y no-linealidad. Sin ambages, quiero sostener la idea según la cual los problemas P vs. NP constituyen la columna vertebral de los estudios en la teoría de la complejidad.
Ahora bien, las ciencias de la complejidad – complexity theory – son ciencia de punta y ciencia de frontera, en toda la línea de la palabra (Maldonado, 2012a). En ellas, de entrada, los problemas combinatorios desempeñan un papel destacado. De manera puntual y franca: las matemáticas de las ciencias de la complejidad son matemáticas de sistemas discretos, y, en consecuencia, los temas referentes a la teoría de la información, los problemas de computación, y las lógicas no-clásicas constituyen, si cabe la expresión, el núcleo mitocondrial del estudio de la complejidad. Y por ello mismo, los problemas formulados por Cook, Karp y Levin.
Los problemas P vs. NP se denotan de distintas maneras en la bibliografía especializada; quizás las dos más genéricas son: P vs NP, P =! NP, y otras más cuyas particularidades pueden ser omitidas aquí de manera provisional.
La puerta de entrada a este grupo de problemas se origina en la obra de K. Gödel, y más específicamente, en la dilucidación de cuáles funciones son computables y cuáles no. El tema de base es el famoso teorema de la incompletud que demuestra que existen siempre algunas proposiciones verdaderas que no pueden ser demostradas. Más sencillamente: hay cosas que sabemos que son verdaderas y no sabemos por qué –o cómo lo son–.
El resultado de Gödel dio origen a una serie de trabajos dedicados, unos a mejorar los métodos, las técnicas y los supuestos de la computación misma;
Lógicas noclásicas constituyen, si cabe la expresión, el núcleo mitocondrial del estudio de la complejidad. Y por ello mismo, los problemas formulados por Cook, Karp y Leviny otros a la lógica, las matemáticas y la teoría de la información. Pero unos y otros nunca han estado completamente aislados entre sí. En otras palabras, el reto formulado a partir de Gödel ha interpelado por igual a la computación aplicada, la teoría de la computación, las matemáticas aplicadas, la lógica en general, y a los propios fundamentos de las matemáticas. No en última instancia, por tanto, también a la filosofía y a la epistemología.
Así, los problemas atañen al análisis numérico, la teoría de la aproximación, la teoría de números computacional, la teoría de sistemas dinámicos, y en las ciencias de la computación, a la teoría formal del lenguaje, la teoría de algoritmos, la teoría de bases de datos, la inteligencia y la vida artificial y la complejidad computacional.
Pero, ¿en qué consisten, propiamente, los problemas descubiertos por S. Cook –el primero–?
Todos los problemas –en la vida como en ciencia– pueden dividirse en dos grupos principales, así: como problemas indecidibles y como problemas decidibles. La decibilidad de un problema hace referencia al famoso décimo problema formulado por D. Hilbert en el Congreso Mundial de 1900 (Gray, 2006), conocido como el problema de detención ( Haltungsproblem ).
Un problema se dice que es indecidible cuando no existe un algoritmo que permita resolver un problema dado, incluso dados tiempo y recursos ilimitados. En consecuencia, no es posible determinar si dicho problema a) se detiene, ni b) cuándo se detiene. La ausencia de cualquier algoritmo aquí significa que el problema no puede ser abordado ni resuelto, básicamente, con la ayuda de fórmulas, reglas, procedimientos, normas o "recetas" ya conocidas y probadas anteriormente, y ni siquiera con cualesquiera otra susceptibles de ser desarrolladas en el futuro. Ejemplos conspicuos de esta clase de problemas indecidibles son: la vida misma, la salud, la equidad, la pobreza, el conocimiento. Los límites de la computación y la lógica conocidas da pie para que pueda pensarse, como es efectivamente el caso, en otros tipos de computación distintos a los conocidos y que se basan en la arquitectura de Von Neumann
y en la tesis Church-Turing (Maldonado, 2012b). Los dos tipos más factibles de computación son la hipercomputación y la computación cuántica. No en última instancia, lo que se encuentra detrás de este tipo de problemas son los retos propios de la criptografía, uno de los capítulos más apasionantes tanto de la computación, las matemáticas y la lógica como de las ciencias de la complejidad.
Los problemas indecidibles constituyen, con total certeza, una de las aristas más apasionantes de la investigación fundamental. No queda la menor duda al respecto. Sin embargo, para efectos prácticos – para retomar la fórmula introducida por J. S. Bell en el contexto de la física cuántica: For All Practical Purposes (FAPP) –, la atención se concentra del lado de los problemas decidibles, que son, si se prefiere, problemas (pragmática o prácticamente) tratables.
Un problema se dice que es decidible, por contraste con los indecidibles, cuando existe –¡o puede existir!– (por lo menos) un algoritmo para su resolución. En otros términos, un problema indecidible es aquel que no se sabe o se puede llegar a saber: a) si se detiene, o bien b) cuándo se detiene. Con base en Hilbert y en la teoría de la computación, esto hace referencia al famoso problema de la detención ( Haltungsproblem ). Incluso, desde otra perspectiva, un problema es decidible cuando es compresible ; la compresibilidad hace referencia a un algoritmo o fórmula en el que un problema –o lenguaje, o programa – puede ser condensado, reducido, comprimido o expresado. Por contraste, los problemas indecidibles son in compresibles .
Pues bien, los problemas decidibles se dividen en dos: los problemas P y los problemas NP. P signifi
ca que el problema es polinomial; es decir, se trata de todos aquellos problemas que pueden ser abordados y resueltos descomponiendo el problema en los términos que componen al problema considerado. Ejemplos de esta clase de problemas son todos aquellos que son trabajados en términos de flujogramas, cronogramas, cladogramas, histogramas, organigramas, y otros semejantes ( charts ). Incluso, de una manera más precisa, es posible decir que los problemas P se abordan y se resuelven en un tiempo polinomial. La unidad física básica de los tiempos polinomiales en la Tierra son los ciclos circadianos.
Como se aprecia, los problemas P son sencillamente todos aquellos con los cuales habitualmente las ciencias y disciplinas normales trabajan, las profesiones y los que son habituales en la vida cotidiana. En matemáticas, esta clase de problemas se dice que son fáciles –porque se resuelven o porque se pueden resolver–. Y en consecuencia, se trata, stricto sensu, de problemas triviales. En verdad, un problema trivial es todo aquel que se resuelve o que puede (llegar a) resolverse. Naturalmente, dados los gráficos – charts – con los que se trabajan, los problemas P son fáciles, triviales, pero no en virtud de los gráficos, sino por la naturaleza misma de esta clase de problemas. La ciencia que se ocupa de esta clase de problemas es, derivativamente, ciencia fácil.
Por su parte, los problemas NP son todos aquellos que son no-polinomiales y que, en consecuencia, ni se abordan ni se resuelven descomponiendo los mismos en los términos que los componen. Y sin embargo, esta clase de problemas se resuelven y deben resolverse en un tiempo polinomial, esto es, en el tiempo práctico que caracteriza a todas las actividades normales de los seres humanos.
Los problemas NP se dice en matemáticas que son problemas difíciles, y por ello, precisamente, se trata de problemas relevantes. En efecto, en lógica y en matemáticas, un problema es relevante si no es fácil, esto es, si no se resuelve o se puede resolver, o no se sabe si puede ser resuelto aun cuando cabe imaginar que, eventual u ocasionalmente, lo será aunque no se sabe cómo, ni cuándo con precisión.
Surge aquí la primera dificultad seria que se encuentra en los fundamentos mismos de los problemas P =! NP. La dificultad se puede enunciar de varias maneras; elijo a continuación la siguiente:

¿Puede decirse que hay más problemas P que NP? Esto es, nos encontramos aquí con la siguiente situación:
P ≥ NP

O bien, inversamente, ¿puede decirse –con certeza o razonablemente– que son más los problemas NP que los P? Es decir,
NP ≥ P

O bien, desde otra perspectiva, puede pensarse en las relaciones entre P y NP en términos de pertenencia o inclusión. Así, ¿cabe afirmarse con verdad que los problemas P pertenecen a, o están incluidos en, NP?
P ∈ NP
O bien,
P ⊆ NP

O acaso, ¿igualmente puede afirmarse la relación inversa?
NP ∈ P

Es decir, ¿puede decirse que los problemas NP pertenecen a los problemas P? ¿O bien, que están incluidos los primeros en los segundos?

Más radicalmente, ¿puede sostenerse razonablemente que los problemas fáciles –P– y los problemas difíciles –NP– son iguales, o quizás, en caso contrario, distintos (Lipton, 2010)?
P = NP
O bien,
P ≠NP

Gráfico 1: Identificación de los problemas P vs. NP

Fuente: Elaboración propia.

Dos tipos de problemas
Problemas Dificiles: Relevantes - Hipercomputación - Computación    no convencional
- Simulación - Metaherísticas

No pueden resolverse algorítmicamente, incluso con recursos de tiempo y espacio ilímitados
Problemas fáciles: Irrelevantes
Decidibles
P N-P
N-P Difíciles
N-P Completos
Indecidibles

2.  Complejidad, innovación, investigación
Pues bien, el trabajo con problemas no es sino una parte de un aspecto más profundo o sensible cuya contracara es la innovación. En efecto, la mejor manera de resolver un problema consiste en innovar; y una manera de innovar es resolviendo problemas.
Sin embargo, surge aquí una dificultad enorme. Se trata del hecho de que en ciencia como en la vida cotidiana, en el sector privado tanto como en el sector público, por ejemplo, en numerosas ocasiones se habla, acaso bienintencionadamente, de innovación, pero en el momento de entenderla en términos prácticos y habituales existe una enorme resistencia al cambio. La innovación implica, manifiestamente, una filosofía del tiempo y del mundo bien determinada, a saber: la pasión por el cambio. No sin razón, ya N. Wiener (1995) distinguía  entre sociedades de conservación y sociedades de innovación; por derivación, digamos, organizaciones, instituciones, empresas, universidades y comunidades en general de conservación y de innovación.
La innovación constituye, a todas luces, el rasgo más destacado de la investigación científica –y otras, como la artística–, en general. Sin desconocer, en absoluto, la importancia de la innovación incremental, el tema de fondo en todo este análisis es la innovación radical ; esto es, la introducción, por primera vez en la historia de la humanidad, de un producto, un servicio, un conocimiento. En otras palabras, el tema de base aquí es el de correr las fronteras del conocimiento, un tema amplio sobre el cual existen tanto indicadores como estudios y conceptos, mecanismos y políticas, a la vez que circunstancias de tipo personal, social y cultural. No en última instancia los temas y problemas en este contexto hacen referencia a cuestiones como innovación social, innovación en organización, de canal, marca y otros semejantes. En este terreno al mismo tiempo confluyen y se diferencian áreas como la ciencia, las políticas educativas, la administración y la política, en fin, la sociología y la economía, principalmente.
Sin duda alguna, la marca de calidad de un fenómeno o sistema cualquiera es el cambio, pero con el reconocimiento explícito de que el cambio introduce, o puede introducir, tranformaciones inesperadas y acaso indeseadas en el sistema en consideración. Simple: un fenómeno o sistema que no cambia no se adapta a los cambios –generalmente provenientes del exterior–. En términos evolutivos, un fenómeno semejante puede encontrarse en peligro de extinción o tornarse endémico. Pero, consiguientemente, tampoco es capaz de innovar, y no ya simplemente de adaptarse a las dinámicas y procesos del entorno. La adaptación es el resultado de demandas de selección, de acuerdo con la teoría de la evolución, pero a su vez, es insuficiente puesto que significa exactamente que el fenómeno es reactivo al entorno, pero carece aún de la capacidad para modificar el entorno al cual se adapta. Carece, digamos, de iniciativa. La innovación es el rasgo mediante el cual un sistema o fenómeno toma sus propias iniciativas y le plantea retos al entorno en general, dejando así, por lo menos de manera provisional, la reacción al entorno.
La ciencia existe en el mundo contemporáneo de una forma específica, que nunca había tenido antes en la historia de la humanidad, a saber: como investigación. Y la investigación descansa en productos. Son productos de investigación artículos científicos (papers), capítulos de libro, libros, patentes y otros semejantes. En este sentido, como es suficientemente sabido, la investigación se lleva a cabo mediante la participación en redes de investigación (circuitos de conferencias, seminarios, congresos, etc.) y con la elaboración de diferentes clases de indicadores de investigación; esto es, ulteriormente, indicadores de innovación. No en última instancia, una arista que surge aquí es la del impacto de la investigación, con el reconocimiento explícito de que existen numerosas formas de evaluar el impacto, y no siempre sucede en términos efectistas y a corto plazo.

3. Algunas conclusiones

Las ciencias, disciplinas, prácticas y oficios se caracterizan, todos, por una cierta heurística –esto
es, su capacidad de resolución de un problema determinado y, dicho de manera genérica, un problema cada vez, en cada momento, según la circunstancia–. El concepto de heurística en este sentido fue formulado originariamente por I. Lakatos en el contexto de la formulación de programas de investigación y de criterios de demarcación entre ciencias y disciplinas. De manera puntual, la heurística se caracteriza por la capacidad de formular o identificar un problema y los medios y procesos posibles o necesarios para resolverlo. Sin ambages, esto es la característica a la ciencia normal –en el sentido kuhniano de la palabra (Kuhn, 1996)–. Otra vía clásica, en esta dirección es el trabajo maravilloso adelantado por G. Polya en su How to solve problems - Cómo plantear y resolver problemas , originalmente publicado en 1945.
Posteriormente, en particular en el contexto del desarrollo de la teoría de la complejidad computacional emergen las metaheurísticas (pero ese es otro tema que merece un espacio propio, aparte y del cual nos ocuparemos en un próximo artículo). Por lo pronto, digamos que estas se ocupan de conjuntos de problemas y la búsqueda de espacios de solución –a lo cual apunta el Esquema 1–. Como quiera que sea, con este texto he querido demostrar qué y cómo los problemas P =! NP constituyen la médula de los temas y problemas relativos a investigación. Con ello, en realidad, se produce un desplazamiento radical de la meto dología de la investigación hacia la lógica y las matemáticas

Esquema 1: Isomorfismos de problemas

Fuente: Elaboración propia.

La dificultad –en rigor la tragedia– en ciencia como en la vida estriba en el hecho de que habitualmente, con las razones y motivos que se quieran, generalmente abordamos siempre primero los problemas fáciles y posponemos los problemas difíciles. La dificultad enorme surge con el reconocimiento de que los problemas difíciles son, al cabo, los verdaderamente relevantes, y que cuando los atacamos, entonces, en numerosas ocasiones, puede ser ya muy tarde.
El Esquema 1 sugiere que en lugar de trabajar en términos de heurística, mejor vale la pena identificar conjuntos de pro blemas. Una manera de identificar conjuntos o clases de problemas es mediante el isomorfismo de los problemas considerados, por ejemplo.
Al trabajar con un conjunto de problemas se abordan espacios de solución. Con el reconocimiento explícito de que al trabajar con espacios de solu
ción no siempre se abordan o se resuelven todos los problemas. En el Esquema 1, es lo que se quiere precisar en el tiempo 1 (t1). En este tiempo se abordan conjuntos de problemas y se buscan espacios de solución (por tanto no ya: un problema en cada momento, o un problema por prioridad, etc.). a, b y c quieren significar que son algunos de los problemas que quedan sin resolver en el t1. Entonces, esta clase de problemas, identificados por ejemplo en función de simetrías o asimetrías y no únicamente de isomorfismos, pueden, conjuntamente con otros afines o semejantes, ser abordados en un t2.
Siempre, por razones de orden lógico, temporal o de recursos, por ejemplo, quedará un pequeño grupo de problemas sin resolver. Pero cuando se trabaja en términos de conjuntos de problemas, con toda seguridad se innova y se resuelven problemas mucho mejor que si se lo hace analíticamente. El t2 designa un pequeño grupo de problemas que han quedado irresolutos –por las razones que se quiera– pero que comparte un cierto rasgo de familiaridad. Se los designa aquí como i, j, k.
Pues bien, son esta clase de problemas, conjuntamente con otros semejantes, los que se trabajarán
en un tiempo t3. Y así sucesivamente. Como se aprecia, en el esquema los elementos e, f, g, designa al pequeño conjunto –subconjunto, en realidad–, de los que no han sido en ese momento abordados en el t3 y que quedarían para el momento o tiempo siguiente.
La explicación y la interpretación no es difícil, como se aprecia. Y sin embargo, en ese dominio genérico que se denomina metodología de la investigación jamás se ha considerado la incorporación de los problemas P vs. NP, un problema que como se aprecia, aporta nuevas luces en la formulación de proyectos de investigación y en el desarrollo de la investigación. Hasta la fecha la atención se ha concentrado en otros aspectos, y no siempre en el más sensible de todos a la hora de investigar: la identificación o formulación de problemas. Digámoslo eufemísticamente: el problema de la investigación.
Como es sabido por parte de académicos, investigadores y gestores del conocimiento, el proceso más difícil y apasionante de todos, y el que toma más tiempo, es, de lejos, el de la identificación o formulación del problema. He querido aquí intentar allanar el camino señalando ante la mirada un territorio generalmente desconocido y por tanto inexplorado en la metodología de la investigación científica.
Pero es preciso hacer una observación puntual: una vez que se entra en los problemas P =! NP, el continente en el que nos encontramos es, de manera específica, el de los entrelazamientos y retroalimentaciones entre matemáticas, lógica y computación. Y en términos generales, más amplios, el dominio que se erige ante la mirada es el de la complejidad, esto es, el de las ciencias de la complejidad. Cabe decir, sin ambages, que en el estudio de los sistemas fenómenos y comportamientos caracterizados por complejidad creciente, los problemas originariamente formulados por Cook, Karp y Levin –pero que han sufrido desarrollos maravillosos hasta la fecha–, constituyen, si cabe la expresión, la columna vertebral de todos los temas y problemas de complejidad.
Dicho de manera puntual: frente a los problemas P vs. NP, cualquier otra preocupación en el contexto de la complejidad del mundo, la sociedad y la naturaleza es quizás derivada o subsidiaria de este, que con justa razón ha sido incluido entre los problemas del milenio.