Probabilidades

¿Qué es más probable? Que alguien que ha tenido un accidente en auto muera ahogado, o que alguien que muera ahogado halla tenido un accidente en auto.
Pongan sus ideas, y les doy la respuesta en unos dias.

Basado en una pregunta de Juegos-Microsiervos.

Haciendo trampa con Lógica, sin hacer trampa

Cuando estaba aplicando para venir a Alemania, tenía que demostrar que tenía conocimiento sobre varios temas de Ciencias de la Computación de los que no había cursado materias específicas. Dado que no había una mejor manera, los representantes en Dresden me pidieron que contestara una especie de examen de admisión que cubría muchos de los temas que requerían.
Tenía únicamente un par de días para contestar todo, por lo que si no sabía algo muy importante sería dificil que lo llegara a contestar correctamente a tiempo.
Todo iba bien, hasta que llegué a una pregunta que me detuvo el corazón:

de los siguientes lenguajes formales, de la mínima n tal que el lenguaje está en C_n según la Jerarquía de Chomsky

y seguía una lista de unos veinte lenguajes que incluían joyas como "el lenguaje de todos los programas escritos en BASIC sin usar ciclos" y otros similares.
Me sentí perdido por un momento. En esos tiempos yo no sabía ni siquiera quién demonios era el tal Chomsky, mucho menos conocía su famosa jerarquía. Incluso pensé en dejar en blanco esa pregunta, pero luego me calmé un poco y decidí ver si podía hacer algo. Así que acudí a la fabulosa Wikipedia y analizé qué era la dichosa jerarquía.
Chomsky simplemente dividió los lenguajes formales en cuatro clases distintas, cada clase más específica mientras se sube en la jerarquía. Entonces ya sabía qué era qué, pero todavía no podía dar la respuesta.
Y esa respuesta se veía muy dificil. Por ejemplo, para saber que algo está en C_2, pero no en C_3, hay que demostrar que el lenguaje no se puede representar por medio de ningún autómata finito - es decir, que no es un lenguaje regular.
Pensé y pensé por un rato; ¿qué iba a hacer con eso? Yo no sabía nada de teoría de autómatas, muy poco de máquinas de Turing formales y aún menos sobre lenguajes como "programas en BASIC sin ciclos".
Y de pronto me empecé a reír. ¡No podía creer mi suerte! Esto no podía ser cierto. Leí y releí la pregunta, pues estaba seguro que ya estaba halucinando, pero no, así estaba escrita.
Recordemos, la pregunta dice: "encuentre la menor n...", mientras que sabemos que C_0 es la categoría más general de la jerarquía. Así que con unas tres líneas di la respuesta para los veinte lenguajes:

para todos los lenguajes en la lista n=0 es la respuesta correcta, dado que todos ellos pertenecen a C_0 al ser lenguajes formales [...]

Así que la lógica me ayudó a hacer trampa para aplicar a la maestría en Lógica Computacional. No sé si la pregunta fue hecha así a propósito o no, lo único que sé es que fui aceptado y aquí estoy, escribiendo sobre teorías que a pocos les interesan.

¡Polinomial es igual a Exponencial!

Digamos que queremos dibujar gráficas completas, o sea, una serie de puntos (nodos) teniendo líneas (aristas) conectando a cada uno de ellos con todos los otros. Tenemos aqui un ejemplo de una gráfica completa de cinco nodos.
Debe ser bastante claro que, si tenemos n nodos, debemos dibujar a lo más n² aristas: por cada nodo, necesitamos dibujar una arista que lo une con cada uno de los otros. En realidad son menos, pero no es mi intención meterme en asuntos de combinatoria ahora, y esta cota es suficiente. Usando lenguaje técnico, tenemos una cantidad polinomial de aristas (contadas sobre el número de nodos).
Pero consideremos ahora el siguiente proceso para dibujar estas aristas: comenzamos con dos nodos conectados entre sí, y luego agregamos otros dos nodos conectados entre sí. Para tener una gráfica completa necesitamos unir cada uno de los dos nodos iniciales con cada uno de los dos nuevos nodos; es decir, necesitamos 4 aristas.(ver las aristas azules en el dibujo).
Ahora continuamos y agregamos otros dos nodos unidos, entonces para cada uno de los cuatro que tenemos del paso anterior, necesitamos agregar dos nuevas aristas, es decir, necesitamos 8 nuevas aristas.
Si continuamos con este proceso, al siguiente paso necesitaríamos 8x2=16 nuevas aristas y al siguiente 32, etc. Pero la cantidad de nodos sólo aumenta de dos en dos, mientras las aristas se duplican, y nunca repetimos una arista; por lo tanto, necesitamos una cantidad exponencial de aristas.
Pero, ¡habíamos visto que solo necesitamos una cantidad polinomial!
¿Alguien encuentra el error?