Historia de la teoría de la complejidad computacional: nuevos primeros pasos.

A raíz de la entrada anterior, en la que hablábamos de Yves Lecerf, y su contribución a las ciencias computacionales, he encontrado este enlace a un capítulo de un libro en el que hablan sobre temas que hoy se incluirían dentro de la teoría de complejidad computacional, pero en realidad antes de que ésta disciplina existiese.

Curiosamente el capítulo del libro (de 1968, año complejo en Francia en otros aspectos), se titula Complexité y el contenido, como ya hemos comentado, es sobre los problemas de complejidad computacional: explosión combinatoria etc…Como veremos el artículo que de alguna manera creó la disciplina como un ente autónomo es de 1965 lo cual explica el uso de estos nombres.

La lista de nombres que aparecen en una historia de la complejidad computacional en el ámbito anglosajón (es decir EEUU; el enlace lo es a un artículo sobre la historia de la teoría de la complejidad computacional, fundamentalmente en EEUU, escrita por uno de sus protagonistas, que además es uno de los editores del primer blog que empezó a publicar sobre estos temas, bien conocido) suelen comenzar con Hartmanis y Stearns (1965), Cobham (1964), Edmonds (1965) y ya, cuando la disciplina madura y toma plena forma, Levin, Cook (la visión de Cook, escrita en 1983; habla de un artículo de Bennett de 1962: Bennett, J. H. On Spectra. Doctoral dissertation, Department of Mathematics, Princeton University, 1962) y Karp con sus bien conocidos respectivos resultados. También se suele / puede incluir a Rabin (1959) como precursor.

Tanto Hartmanis (Hartmanis, J. January 1981. Observations about the development of theoretical computer science. Annals of the History of Computing, Volume 3, Number 1, pp. 42-51. ) como Stearns han escrito sus respectivas versiones del periodo en el que fueron protagonistas.

En otras tradiciones como la soviética, como mucho se remontan a los 50 (Trakhtenbrot, de este mismo autor es la historia de la teoría de la complejidad computacional en la Unión Soviética que aparece en el enlace anterior, titulada A Survey of Russian Approaches to Perebor (Brute-Force Search) Algorithms ). Por cierto Levin pertenece a esta otra tradición, sobre la que hablaremos luego de nuevo.

Nota. Cabe preguntarse en que medida el interés que surgió en paralelo en estos temas a uno y otro lado del telón de acero fueron producto de la Guerra Fría. Llama por ejemplo la casi total ausencia de europeos occidentales entre los pioneros. También por su diferente recepción a uno y otro lado.

Extracto.

It is not surprising that we were attracted by the same problems as our colleagues in the West (of course, we were working independently and in parallel), and we worked out almost the same techniques: complexity measures, crossing sequences, diagonalization, gaps, etc. All of these ideas arose quite naturally; we became most excited, and they evoked in us enthusiasm similar to that described by Hartmanis in his historical account (1981).

Fin de nota.

En el artículo sobre el que hablamos desde el principio nos hablan de otras épocas y otros nombre que no había visto asociados a esta disciplina:

a) Lindenbaum, publicación del Congreso Internacional de Filosofía en París, 1935. Concretamente se refiere a:

  • Lindenbaum, A. 1936, “Sur la simplicité formelle des notions”, in Actes du Congrès International de Philosophie Scientifique, VII Logique (Acutalités Scientifique et Industrieles 394), 29–38.

Extracto.

Two papers—Lindenbaum 1936 and Lindenbaum–Tarski 1934–1935—should be particularly mentioned. The former paper,  is Lindenbaum’s contribution to the already mentioned Paris Congress in 1935,; concerns the formal simplicity of concepts. Although Lindenbaum points out that this question arises in many fields, he does not offer any general definition of simplicity. Lindenbaum distinguishes seven relevant problems concerning simplicity (a) of systems of concepts (terms); (b) of propositions and their systems; (c) of inference rules; (d) of proofs; (e) of definitions and constructions; (f) of deductive theories; (g) of formal languages; but he addresses his further considerations to (a). The idea is that measuring the number of letters occurring in a given concept can tell us about the simplicity of the term (Lindenbaum follows Leśniewski in this respect). Two points are interesting. First, Lindenbaum assumes the simple theory of types.  This suggests that he preferred a more elementary construction if it is possible and adequate for a given problem. This attitude was also very popular among Warsaw mathematicians and logicians. Second, Lindenbaum observes, obviously under Tarski’s influence, that simplicity has not only a syntactic dimension (in Carnap’s sense), but it should also be considered semantically. Fuente. Realmente, el contenido del artículo de 1936 es bastante tangencial a la teoría de la complejidad computacional.

b) Nelson Goodman, 1943.  Hemos hablado recientemente de este autor, en este blog, pero en otro contexto, citando uno de sus libros. En el libro seguramente se refieren a este artículo:

Goodman, Nelson (1943). On the simplicity of ideas. Journal of Symbolic Logic 8, pp. 107–21.

Abstract. The motives for seeking economy in the basis of a system are much the same as the motives for constructing the system itself. A given idea A need be left as primitive in a system only so long as we have discovered between A and the other primitives no relationship intimate enough to permit defining A in terms of them; hence the more the set of primitives can be reduced without becoming inadequate, the more comprehensively will the system exhibit the network of interrelationships that comprise its subject-matter. Of course we are often concerned less with an explicit effort to reduce our basis than with particular problems as to how to define certain ideas from others. But such special problems of derivation, such problems of rendering certain ideas eliminable in favor of others, are merely instances of the general problem of economy. Thus it is quite wrong to think of the search for economy as a sort of game, inspired by an abnormal love of superficial neatness. Some economies may be relatively unimportant, but the inevitable result of regarding all economy as trivial would be a willingness to accept all ideas as primitive at the outset, making a system both unnecessary and impossible.

Se trata de A modified and expanded version of a paper On the length of primitive ideas, of which an abstract appeared in this Journal, vol. 8 (1943), p. 39. The paper was scheduled for the meeting of the Association for Symbolic Logic that was to have been held at Yale University in December 1942.

Goodman y sus seguidores (según nos comentan en el libro, Kemeny, Svenonius, Suppes) intentaron crear una teoría de la simplicidad, vinculada a la filosofía de la ciencia.  No tengo acceso a ninguno de los dos artículos citados y no tengo muy clara su vinculación con la teoría de la complejidad computacional. Claramente el campo no estaba totalmente definido en 1968 cuando se escribió el capítulo que ha dado pie a la presente entrada.

c) [Von Neumann (1949), Nash (1955)] y Gödel (1956):D´ailleurs, l´idée  de  d´utiliser la  notion de “longueur d´une démonstration” éstait présente chez Godel dès 1930“). Su carta a V. Neumann de 1956 es bien conocida…Nada nuevo aquí.

Pero si es nuevo para mi un artículo que nos muestra la visión de Von Neumann (en publicaciones anteriores a la carta de Godel) sobre los temas sobre los que hablamos.

Título: Von Neumann, G¨odel and Complexity Theory Alasdair Urquhart∗ Department of Computer Science University of Toronto June 23, 2010

Abstract. Around 1989, a striking letter written in March 1956 from Kurt G¨odel to John von Neumann came to light. It poses some problems about the complexity of algorithms; in particular, it asks a question that can be seen as the first formulation of the P=?NP question. This paper discusses some of the background to this letter, including von Neumann’s own ideas on complexity theory. Von Neumann had already raised explicit questions about the complexity of Tarski’s decision procedure for elementary algebra and geometry in a letter of 1949 to J.C.C. McKinsey. The paper concludes with a discussion of why theoretical computer science did not emerge as a separate discipline until the 1960s.

La última frase, que se puede enmarcar dentro de la sociología de la ciencia, de alguna manera relacionada con nuestro comentario en una nota anterior, dentro del mismo marco. Algunos extractos del artículo sobre este tema:

Modern theoretical computer science is a remarkable confluence of several different intellectual traditions, and in its early development it attracted researchers from mathematics, physics, engineering, logic and linguistics. The nascent science of algorithms, however, would have been stillborn without two external stimuli, first the rapid development and diffusion of computer technology in the 1950s, and second, the establishment in the 1960s of separate and independent departments of computer science, in response to the demand created by the first stimulus. The years 1956 and 1957 are especially significant in the diffusion of computers and their availability to students and researchers.

The year 1957 was also the year of the famous Cornell Summer Institute already mentioned in connection with the computer implementations of Martin Davis and George Collins; some of the history of this conference can be found in Halmos’s reminiscences [21, pp. 215-216] and the Fefermans’ biography of Tarski [16, 220-230]. No fewer than eighteen of the eighty-two talks summarized in the proceedings are more or less directly connected with computer-related questions – this is without counting the work of Rabin and Scott on finite automata that was to prove highly influential in the early development of theoretical computer science. The conference also included four talks on programming systems, including one by Peter Sheridan of the IBM Corporation on the “Fortran Automatic Coding System” [37]. In spite of the anticipations of some of the main concepts of complexity theory by von Neumann and G¨odel, these ideas, it seems, could not form part of a generally accepted mathematical research program until the wider spread of computer technology had provided the foundation.

Y muy en linea con nuestro comentario:

In spite of the separation of research communities caused by the Cold War, the development of complexity theory in the Soviet Union followed remarkably similar lines to those in the U.S.A. In the Soviet Union, research on the complexity of switching networks continued through the 1950s, the work of Shannon providing some of the earlier inspiration. Even earlier than in the West, Soviet scientists recognized the key importance of the question of whether brute force search (“perebor”) was unavoidable in some cases. In fact, there was even a claim by Yablonski in 1959 to have proved its unavoidability; a detailed account of this intriguing episode is given by Boris Trakhtenbrot [40]. Yet in Russia, just as in the U.S.A., we find isolated attempts that do not grow into a full research programme. Trakhtenbrot reports [40, p. 391] that as early as 1956 G.S. Tseitin, at the time a 19-year-old student of Markov at Leningrad University, proved nontrivial lower and upper bounds on the complexity of some concrete problems in the context of Markov’s normal algorithms. However, Tseitin’s results remained unpublished. The proposal to identify feasible with polynomial time algorithms appeared in the 1960s in the work of Cobham [7], Edmonds [14] and Rabin [33]. The framework in which to pose the most basic problem about “perebor” algorithms, that of NP-completeness, does not emerge until the early 1970s, with the independent work of Cook [10] and Levin [27].

En definitiva este autor afirma que una teoría de la complejidad computacional emergía allí dónde el uso de computadores empezaba a generalizarse en determinados círculos (académicos, centros de investigación públicos o privados etc…).  Tiene que ser así, pero no deja de ser paradójico: parecería que más sentido tiene una teoría de este tipo, de cuanto menos recursos computacionales se disponga. Si tengo que calcular a mano (de hecho Turing, que publicó sus resultados sobre máquinas de Turing, antes de que existiesen computadores electrónicos, tenía en la cabeza un calculador humano, que trbajaba con lápiz y papel), más sentido tiene que me centre en la eficiencia de los algoritmos y que intente obtener una teoría al respecto. Sin embargo no fue así.  Parecería que para el calculador humano, todo cálculo es abrumador, no hay diferencia entre polinómico y exponencial y sólo cuando emergen las máquinas electrónicas, no abrumadas por ningún tipo de cálculo, empiezan a tener sentido este tipo de análisis.

Por otra parte, aunque  me gustaría leer más literatura al respecto, llama la atención que en el mundo  soviético el problema que aparentemente centrase toda la atención cuando se hablaba de perebor era el de minimización de circuitos booleanos, y no por ejemplo problemas de programación lineal, que también se desarrolló en paralelo a los dos lados del telón de acero.

Sobre esto Dantzig, que en PL juega el papel, digamos  de Hartmanis, nos comenta (muy interesante artículo): What seems to characterize the pre-1947 era was lack of any interest in trying to optimize. T. Motzkin in his scholarly thesis written in 1936 cites only 42 papers on linear inequality systems, none of which mentioned an objective function.

The major influences of the pre-1947 era were Leontief’s work on the Input-Output Model of the Economy (1933), an important paper by von Neumann on Game Theory (1928), and another by him on steady economic growth (1937). My own contributions grew out of my World War II experience in the Pentagon. During the war period (1941– 45), I had become an expert on programming-planning methods using desk calculators. In 1946 I was Mathematical Advisor to the US Air Force Comptroller in the Pentagon. I had just received my PhD (for research I had done mostly before the war) and was looking for an academic position that would pay better than a low offer I had received from Berkeley. In order to entice me to not take another job, my Pentagon colleagues, D. Hitchcock and M. Wood, challenged me to see what I could do to mechanize the planning process. I was asked to find a way to more rapidly compute a time-staged deployment, training and logistical supply program. In those days “mechanizing” planning meant using analog devices or punch-card equipment. There were no electronic computers.

En el  mismo artículo Dantzig comenta muy por encima sobre complejidad computacional. Si bien el modelo LP y su primera solución algorítmica, el método del simplex fue occidental, algunos de los avances algorítmicos(Khachiyan, 1979), se hicieron al otro lado del telón de acero. Posteriormente el testigo pasó de nuevo a occidente con Karmarkar, en 1984 (aunque de origen indio hizo su trabajo en EEUU).

Otros dos enlaces relacionados con la historia de la programación lineal:

On the history of combinatorial optimization (till 1960). Alexander Schrijver1.

Different Motivations and Goals in the Historical Development of the Theory of Systems of Linear Inequalities. Tinne Hoff Kjeldsen. Este problema no es exactamente el  mismo que aborda la programación lineal, pero es interesante seguir su historia.

Al igual que entre los prácticos y teóricos de la informática unos años más tarde, ya a primeros de los 50 entre los (sobre todo) prácticos y teóricos de la planificación programada se era consciente de consideraciones relacionadas con la complejidad computacional. Algunos extractos lo demostrarán:

Extractos.

–Kantorovich (¿1939?).  In the simplest case of one or two variables such problems are easily solved—by going through all the possible extreme points and choosing the best. But, let us say in the veneer trust problem for five machines and eight types of materials such a search would already have required solving about a billion systems of linear equations and it was evident that this was not a realistic method. I constructed particular devices and was probably the first to report on this problem in 1938 at the October scientific session of the Herzen Institute, where in the main a number of problems were posed with some ideas for their solution.

Thorndike (1949). The assignment problem has helped in gaining the insight that a finite algorithm need not be practical, and that there is a gap between exponential time and polynomial time.

Also in other disciplines it was recognized that while the assignment problem is a finite problem, there is a complexity issue. In an address delivered on 9 September 1949 at a meeting of the American Psychological Association at Denver, Colorado, Thorndike [1950] studied the problem of the ‘classification’ of personnel (being job assignment):

“The past decade, and particularly the war years, have witnessed a great concern about the classification of personnel and a vast expenditure of effort presumably directed towards this end”.

He exhibited little trust in mathematicians:

“There are, as has been indicated, a finite number of permutations in the assignment of men to jobs. When the classification problem as formulated above was presented to a mathematician, he pointed to this fact and said that from the point of view of the mathematician there was no problem. Since the number of permutations was finite, one had only to try them all and choose the best. He dismissed the problem at that point. This is rather cold comfort to the psychologist, however, when one considers that only ten men and ten jobs mean over three and a half million permutations. Trying out all the permutations may be a mathematical solution to the problem, it is not a practical solution”.

Thorndike presented three heuristics for the assignment problem, the Method of Divine Intuition, the Method of Daily Quotas, and the Method of Predicted Yield. (Other heuristic and geometric methods for the assignment problem were proposed by Lord [1952], Votaw and Orden [1952], T¨ornqvist [1953], and Dwyer [1954] (the ‘method of optimal regions’).)

Von Neumann (1950,1951). Von Neumann considered the complexity of the assignment problem. In a talk in the Princeton University Game Seminar on October 26, 1951, he showed that the assignment problem can be reduced to finding an optimum column strategy in a certain zero-sum twoperson game, and that it can be found by a method given by Brown and von Neumann [1950]

The method of Brown [1951] to determine the optimum strategies is that each player chooses in turn the line that is best with respect to the distribution of the lines chosen by the opponent so far. It was proved by Robinson [1951] that this converges to optimum strategies. The method of Brown and von Neumann [1950] is a continuous version of this, and amounts to solving a system of linear differential equations.

According to a transcript of the talk (cf. von Neumann [1951,1953]), von Neumann noted the following on the number of steps: “It turns out that this number is a moderate power of n, i.e., considerably smaller than the “obvious” estimate n! mentioned earlier”.

–Beckman y Koopmans (1953).

In a Cowles Commission Discussion Paper of 2 April 1953, Beckmann and Koopmans [1953] noted: It should be added that in all the assignment problems discussed, there is, of course, the obvious brute force method of enumerating all assignments, evaluating the maximand at each of these, and selecting the assignment giving the highest value. This is too costly in most cases of practical importance, and by a method of solution we have meant a procedure that reduces the computational work to manageable proportions in a wider class of cases.

–Kuhn (1955), Munkres (1957), Ford & Fulkerson (1956),

Kuhn [1955b] contented himself with stating that the number of iterations is finite, but Munkres [1957] observed that the method in fact runs in strongly polynomial time (O(n 4 )). Ford and Fulkerson [1956b] reported the following computational experience with the Hungarian method:

“The largest example tried was a 20 × 20 optimal assignment problem. For this example, the simplex method required well over an hour, the present method about thirty minutes of hand computation”.

Los ejemplos anteriores ponen de manifiesto el fenómeno que ya hemos comentado en otras entradas, y que seguramente habrán experimentado el 100% de los investigadores en estos temas. Cuando uno estudia problemas de optimización combinatoria, por poner un nombre general, enseguida se da cuenta de varias cosas:

–que existe para ellos una solución obvia de fuerza bruta, de búsqueda exhaustiva;

–que la solución de fuerza bruta enseguida (incluso para pequeños tamaños del problema) es imposible de implementar;

–en este momento surge la pregunta sobre si no habrá una solución más eficiente que la de fuerza bruta o búsqueda exhaustiva;

–lo cual lleva a algunos a buscar una solución más eficiente para estos problemas concretos;

–el último paso, paso que pocos han dado, sería ya una teoría de la complejidad computacional, Esto es, tras tomar distancia, plantearse la metapregunta: ¿ hay problemas intrínsicamente complejos en los que el único o mejor método de solución posible, el óptimo, es el uso de la fuerza bruta ?. Entiendo que esta pregunta, aunque puede confundirse con ella,  es ortogonal a la distinción entre algoritmo polínomico y exponencial: ¿ no puede haber casos en los que la fuerza bruta implica una búsqueda  polinómica con respecto al tamaño del input ?.

Relevante para la pregunta anteriorLet us say that an algorithm is “brute force” if it accomplishes the job of finding one solution by finding them all — it has no idea how to do any better. However, it does achieve polynomial running time if certain parameters are assumed constant e.g., for CLIQUE, when restricted to graphs having cliques of  size at most k (a constant), there is a trivial O(n^k) algorithm.

Y también relevanteare all brute force algorithms exponential in run time? No, certainly not. Consider a linear search algorithm to search a sorted array. You can do better, but a linear search could be considered “brute force”.

Y otro enlace relevante sobre el mismo tema, en el que nos informan sobre algunos problemas de fuerza bruta polinómica:

1. Maximum sub array problem
  – brute force is o(n^2)
  – kadane’s algorithm it is o(n)
2. Multiplication
  – brute force will take O(n^2)
  – Toom-cook multiplication or karatsuba O(n^1.58)
3. Sorting
  – brute force just swapping two numbers O(n^2)
  – Tim sort or 3-way quicksort O(nlgn) 

Realmente la ya tan asentada distinción entre (algoritmo) exponencial y polinómico es polémica, por varios motivos en los que no vamos a entrar. A mucha gente le parece un corte arbitrario cuando se encuentra con él por primera vez, y los argumentos que se aportan para su existencia parecen más ad-hoc que consistentes.  ¿ No es más natural, menos arbitraria, aunque quizás más gradual que dicotómica, una distinción fuerza bruta / método digamos directo que obvia la búsqueda exhaustiva ? ¿ Existen problemas de fuerza bruta polinómica en los que la solución por fuerza bruta es inevitable ? Temas a estudiar.

Seguramente la distinción fuerza bruta polinómica /métodos directos polinómicos ya está capturada por clases de complejidad dentro de P. También de interés serían los problemas en los que, demostrablemente, la mejor solución posible sea la fuerza bruta exponencial. ¿ Existen ? ¿ Hay alguna clase de complejidad que los capture ? No me queda claro si las elevadas Exp o Nexp completas o no capturan esta clase de problemas (tengo muy oxidados mis conocimientos al respecto). Y realmente habría que comenzar por definir que se entiende exactamente por fuerza bruta ( intuitivamente, búsqueda exhaustiva en el espacio de soluciones posibles).

Según estoy viendo, en este contexto siempre se cita el problema de buscar un número con una propiedad dada que lo haga único, entre un conjunto de números dados (por ejemplo buscar el  mínimo entre una lista de 100 números diferentes) como el ejemplo trivial de un problema cuya mejor solución es la fuerza bruta polinómica. Intuitivamente la situación parece clara, pero no sé no sé. Un buen comienzo sería analizar en detalle este problema (el input, las posibles medidas de su tamaño, el problema definido sobre este input, si la comprobación de la solución se puede hacer de manera más económica que su búsqueda (aparentemente no),  etc…) y buscar variantes exponenciales.

De hecho seguramente es uno de los problemas más analizados (técnicamente se llamaría search an unsorted array o linear search). Se conoce su complejidad óptima clásica y ¿ cuántica ? (algoritmo de Grover; no tengo claro cual es el input de este algoritmo y si es equivalente al de linear search clásico). Ver también la entrada sobre linear search en wikipedia. De interés también: Exact algorithms for NP-Hard problems: a survey  y más reciente del mismo autor, Open problems around exact algorithms.   Me pregunto si este problema no sería un buen pilar sobre el que construir una teoría de complejidad alternativa, basada en el concepto de fuerza bruta…Lo dejamos como pregunta. 

Actualización día siguiente.

No es que ahora quiera dedicarme a construir una teoría de complejidad computacional alternativa, pero le he dado  una par de vueltas con la almohada.

El objetivo de la teoría es obtener un test rápido, tal que, dado  un input y un problema asociado, determinar lo más rápidamente posible si es posible solucionarlo de manera más eficiente que con fuerza bruta o no es posible, independientemente de que esta sea logarítmica, lineal, polinómica o exponencial. Si el resultado del test es que es posible, entonces merecería la pena invertir tiempo en encontrar una solución más eficiente. El objetivo es ambicioso: me temo que un test de este tipo sería equivalente a la solución del problema central de la teoría de complejidad computacional hoy.

El modelo que tengo en mente de momento es:

–de tipo opaco (black box), es decir el que usa el computador no tiene acceso a la lista (o a cualquier otro input) directamente sino sólo a través de demandas posicionales;

–las demandas o queries serían del tipo “dame la  entrada que está en la primera posición de la lista”. Estas serían la  unidad de cuenta. Se pueden dar instrucciones complejas pero extraer una entrada de cada posición cuenta como una unidad.

–como partes tenemos el computador, que se encuentra en una sala aislada y con el que solo se puede comunicar mediante demandas, y hay dos tipos de usuario del computador: el directo, que se encuentra en la sala continuamente y va pidiendo las demandas y otro (digamos el verificador), que entra en la sala y al que hay que demostrar de la manera más eficiente posible, mediante demandas al computador del que el va a ser testigo, que la respuesta al problema es correcta.

–el upper bound es siempre la búsqueda exhaustiva o fuerza bruta, concepto que habría que definir claramente (yo no tengo una definición clara ahora mismo), expresado en las unidades de cuenta de queries,  y la medida de la complejidad del algoritmo sería el ahorro conseguido con respecto a este upper bound. Nos interesa conocer la complejidad de los algoritmos tanto para la computación directa como para la verificación.

Ejemplo 1:

Input: lista de n números diferentes. Sólo el computador los conoce.

Problema: demostrar que un número dado a la parte directa está en la lista o no.

Complejidad óptima de la computación de la parte directa:  n demandas.

–Complejidad de la verificación: 1 demanda (si está en la lista, cosa que el directo conoce, bastará con pedir al computador que extraiga la entrada de la posición que contenga el numero). Nótese que solo se pide demostrar que está en la lista, no que no está, en cuyo caso la complejidad sería diferente.

Ejemplo 2.

–input: lista de n números diferentes.

–problema: se le da un número contenido en la lista al directo y debe de demostrar si es el máximo o no lo es.

–complejidad directa: n demandas. Para ver si es el máximo tiene que extraer todos los números y hacer la comparación con el número dado (de momento no tenemos en cuenta el coste  de estas comparaciones).

–complejidad de verificación: en este caso no hay atajos en la verificación. n demandas también.

Como se ve la complejidad directa y la de verificación en un caso difieren y en el otro ambas son iguales, no hay manera, si no estoy equivocado, de superarla fuerza bruta. El lector que conozca la teoría de complejidad al  uso no verá, creo, nada nuevo. Esta diferencia se corresponde con una de las caracterizaciones (en parte) de los problemas NP (ejemplo1) y los problemas  en los que la verificaciones no son más sencillas que la búsqueda de la solución, con la salvedad de que en este caso las dos son lineales.

También se pueden plantear problemas más complejos que impliquen hacer cosas con varios números a la vez,  como sumas por ejemplo. Pero estos dos problemas (u otros similares más adecuados, según se vaya viendo), cuya complejidad se puede tomar como axioma (es decir algo casi evidente, que no necesita demostración) serían los primitivos, aquellos que sirven para ejecutar el resto de problemas y determinar su complejidad (es decir determinar si es posible superar la fuerza bruta). Si el  resultado para un problema dado es que no es posible superar la fuerza bruta dentro de este modelo, quiere decir que la única manera de superarla sería conseguir superarla en los problemas primitivos, es decir demostrar que el axioma es falso.

Un ejemplo de problema que implica una comprobación con varios números de de la lista, que diría permite mejorar la búsqueda exhaustiva y que pone de manifiesto que le falta algo al modelo:

Ejemplo 3.

–Input: una lista de m números sin ordenar. suponemos m=4

–Problema: dado un número n, comprobar si existe un par de números de la lista que sumen n. Suponemos que n es superior a la suma de cualquier par de la lista de m numeros, pero ni el director ni el supervisor lo saben. suponemos n=8

–complejidad búsqueda exhaustiva: generar y comprobar la suma de (m(m-1))/2 pares de números diferentes. Hay que calcular el coste de esto en unidades básicas. Generar cada par de números son 2 operaciones básicas. 2m(m-1)/2 = m^2-m cuesta generar todos los pares. ¿ cuantas unidades básicas supone una suma cuando ya tienes fuera los dos elementos ?.   Esto es una de las cosas que faltaría por definir. Luego fuerza bruta = coste de generar los pares+coste de realizar las sumas x número de pares =

–complejidad directa:  no tengo claro cual es la manera óptima de resolver el problema entiendo que no es complicado superar la fuerza bruta, al  menos cuando n no se puede sumar con dos números de la  lista. Un primer método nos indica que bastaría con ordenar la lista, coger los dos más grandes y ver si suman n o no. Pero ordenar (sorting) ya es una operación compleja y costosa. Mejor simplemente repetir la operación de buscar el máximo de la lista 2 veces (la segunda con m-1 items) y sumarlo.  n+n-1 = 2n-1+ coste de la suma de este par.

–complejidad de verificación:  Para demostrar al verificador podemos repetir el  método de búsqueda, igualandolo, pero ¿ podemos mejorarlo ?. Parece que no, pero entiendo que dependerá de lo que se permita almacenar al director en la memoria de fuera del computador. Este es otro tema que falta por definir.

Este es un problema en el  que la complejidad de la fuerza bruta es polinómica y la complejidad directa y de verificación son lineales. Ahora me gustaría poder identificar un problema similar, natural, de complejidad fuerza bruta polinómica y que se pueda demostrar de que su complejidad directa es idéntica a la de fuerza bruta. Y lo mismo, pero con complejidad exponencial (tras hacer memoria, casi seguro que los problemas con complejidad temporal de fuerza bruta, directa y de verificación exponencial, es decir literalmente 2^n están capturados por la clase EXPTIME; serían equivalentes en el nivel exponencial al problema del ejemplo 2; los problemas en NEXP son aquellos que tienen complejidad de verificación exponencial, es decir 2^n,  pero complejidad directa que podría ser superior, por ejemplo 2^2^n).

Y finalmente otro tema que falta por definir es el input y el problema. Parece  que salen de la nada. Estoy tentado a crear otra parte que se encargue de esto, el imputador, que igual podría coincidir con el verificador…

Seguramente nada de esto es nuevo y seguramente este modelo es equivalente a lo que ya existe. Lo averiguaré cuando tenga tiempo. Como nombres de las tres partes se me ocurren el computador, director y supervisor.

Fin de actualización.

Nota. Un extracto del artículo de Urquhart sobre Von Neumann y Gödel citado nos enlaza con la anterior entrada en el blog, en la que un artículo combina consideraciones termodinámicas con la teoría de la complejidad computacional.

By contrast, von Neumann envisages a theory of automata that is more like thermodynamics than discrete mathematics;

“All of this will lead to theories which are much less rigidly of an all-or-none nature than past and present formal logic. They will be of a much less combinatorial, and much more analytical, character. 5 In fact, there are numerous indications to make us believe that this new system of formal logic will move closer to another discipline which has been little linked in the past with logic. This is thermodynamics, primarily in the form it was received from Boltzmann, and is that part of theoretical physics which comes nearest in some of its aspects to manipulating and measuring information. Its techniques are indeed much more analytical than combinatorial, which again illustrates the point that I have been trying to make above [42, p. 304]”.

Lo que hemos puesto entre comillas forma parte de una carta de Von Neumann.

Otro extracto nos muestra lo pragmática que era la mente de Von Neumann cuando pensaba sobre estos temas.

In reply, von Neumann observed that such problems could also be solved by a general purpose digital computer, but that

“the mere observation that a particular type of finite problem can be solved with either type of machine is not very relevant. . . . The crucial question is that of the time required for the solution.”

“Let N be the number of steps required by Tarski’s decision method in the case of either one of the problems. N is, of course, a function of n and r. What kind of a function is it? How rapidly does it increase? How large is it for moderately large values of n and r? Or conversely: In what range can n and r be chosen without giving prohibitively large N’s? [34, p. 179]”

He goes on to discuss the speedup in computation that could be attained through the use of computers, and estimates that a speedup of the order of 10^4 to 10^5 over human computers could be attained. This figure of 10^5 then represents an upper bound on the complexity of problems suitable for solution by machine.

“My skepticism regarding the suitability of any variety of machine which is at this moment in sight for combinatorial-logical problems is just due to this: I suspect that while the five powers of 10 referred above include a lot of territory in the sense of problems of a mathematical-analytical character, they cover very little material in the case of combinatorial-logical problems. I am inclined to believe this – until I see a proof of the opposite – because the number of steps that are needed to solve a problem increases with the characteristic parameters of a problem much more quickly for problems of a high logical type than for others of a lower type. This is a rather natural conclusion from the old work of K. G¨odel. Now ordinary mathematical-analytical problems are never of a high logical type: They are usually of the next type after that one of the arithmetical fundamental variable. Logical-combinatorial problems like those which you mentioned in your letter, on the other hand, are almost always of a higher type. I have not determined the type of either one of your problems, but I suppose that it will be the second or third one above the arithmetical fundamental variable [34, p. 179]”.

No le cabe en la cabeza el enfoque asíntotico que asume la actual teoría de la complejidad. Al final cualquier computador será  limitado en la práctica y más que un enfoque asíntotico interesa un enfoque de tipo listón.

Muy interesante este artículo. Terminamos con un extracto que nos indica que Von Neumann no siempre acertaba y que su acercamiento a las ciencias sociales fue más bien abstracto y no basado en un conocimiento real de los individuos cuando actúan en el marco de instituciones sociales; su idea del individuo sería más una entrada en una fila o columna de una matriz siendo la institución social la propia matriz; no tendría en mente a un individuo de carne y hueso sujeto a la racionalidad homeostática sobre la que tanto hemos escrito:

He insisted that the new technology be made freely available outside the realm of commercial patents, and as a result, the IAS 12 computer was widely copied, its direct descendants including the AVIDAC, the ILLIAC, the JOHNNIAC and the IBM 701 [2, p. 91]. For this reason alone, von Neumann must be considered one of the most important founders of modern computer science.

Fin de nota.

Para que el punto que corresponde a ilustres predecesores  sea completo  añadimos las consideraciones sobre la complejidad de determinados sistemas criptográficos que hizo Nash en 1955, tema sobre el que hicimos una entrada en su momento y sobre el que nos ilustra uno de los autores que más ha publicado sobre la disciplina sobre la que hablamos, David Johnson. Y otro artículo de contenido similar, de Sipser.

d) La “escuela soviética”.

Y también de lo que se hacía en la URSS un poco más tarde, con nombre de nuevo inéditos para mi: Iablonski o Lupanov et bien d´autres.

En el artículo de historia del perebor en la URSS enlazado anteriormente, hablan con bastante profundidad sobre Iablonski o Yablonski y de otros. Mucho menos de Lupanov. El primero tiene el (seguramente dudoso) honor de haber publicado la primera solución (no aceptada finalmente) al famoso problema central de la disciplina sobre la que hablamos.

e) Otros pioneros (que yo desconocía).

También hablan de los que normalmente se consideran pioneros: Ritchie, Yamada, Schutzenberger, Trakhtenbrot, Rabin…(en negrita los nuevos para mi, sobre los que comento en detalle en lo que sigue).

–Por Ritchie entendemos que se refiere a Dennis Ritchie, en su colaboración con Meyer y no a R.W Ritchie, que publicó más bien sobre teoría de computabilidad. Ambos publicaron en los 60. El primer Ritchie es bien conocido.

ritchie

Fuente de la imagen: libro Theories of Computational Complexity.

Schutzenberger.  Entendemos que se refiere a Marcel-Paul,  que en cuanto a trayectoria científica es parecido a Lecerf, pero a la inversa: empezó como médico y acabó desarrollando actividad como matemático. El concepto de monoide pláctico, estructura sobre la que trabajó este autor y que yo no conocía, suena un poco a concepto médico para el no iniciado, pero en realidad no tiene nada que ver con la medicina (lo de pláctico proviene de la geología). Este tipo de carreras parecen ser más posibles en Francia, país que gusta de la generalidad y dónde los investigadores, a diferencia de en EEUU no buscan ser genios en apretar una tuerca de un tipo muy específico de una determinada manera. También eran otros tiempos y no voy a ser yo quien tire la primera piedra contra la división del trabajo…. Bueno al grano: ¿ cual fue la contribución de este autor a la teoría de complejidad computacional ?. El artículo de St Andrews University sobre este autor no nos aclara demasiado al respecto. Sí aclara que al parecer este autor, sobre el que yo no había oído hablar,  además de prolífico hizo importantes contribuciones. Su lista de publicaciones hasta 1969. Según he visto en un conocido blog parte de su producción relativa a lenguajes formales se puede enmarcar dentro de lo que hoy se denomina complejidad computacional.

Extracto. 

In the 1960’s one of the main focuses of people working on, what we call complexity theory today, was language theory. This was the study of regular languages, context-free languages, and context-sensitive languages. These correspond, of course, to finite automata, to non-deterministic pushdown automata, and to linear bounded non-deterministic machines. The rationale for this interest was driven by Noam Chomsky and Marcel-Paul Schützenberger, especially Chomsky who was interested in a theory of “natural langauges”. At the same time programming languages, such Algol 60, were beginning to appear that needed a theory to support compiler construction.

Language theory was an important source of questions for theorists. One the so called LBA problem, I have already discussed in an earlier post was raised in the 1960’s and took almost thirty years to get solved. Many other problems from language theory played an important role in shaping theory’s direction at the time.

Intentaremos averiguar sobre la contribuciones de estos autores a la teoría (primitiva) de la complejidad computacional, e iremos actualizando. ¡¡ Hecho !!

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: