Algorítmica y complejidad computacional. i.o. SUBEXP.

Disclaimer. El problema para publicar entradas en el blog se resolvió finalmente mucho más rápido de lo que esperaba y sin necesidad de ayuda externa. Los foros fueron suficientes.

Tras publicar en forma de comentarios, volvemos a la forma  de publicación habitual. En este nuevo periodo del blog nos vamos a centrar sobre todo en el mismo tipo de publicaciones que en la primera fase (dos primeros años) del blog. No obstante paramayor organización, vamos a seguir actualizando en los comentarios.  Fin de disclaimer.

Antes de volver a mancharnos las manos con el lápiz y la goma para rematar los flecos que quedan dentro de nuestra investigación (esto es necesario para la siguiente y última fase del proyecto y espero resolverlos pronto o no resolverlos y pasar a siguiente fase de cualquier manera), calentamos motores poniéndonos al día en complejidad computacional (por una parte me sigue costando leer sobre estos temas, por otra parte en esta última ronda estoy llegando más lejos en la comprensión de algunos temas; así es la madurez).

Conozco hoy por primera vez una clase, i.o. SUBEXP (infinitely often SUBEXP) aparentemente

bastante artificial, pero que a mi me ha parecido a primera vista interesante. Es la indicada en el título y en este paper se publicó por primera vez.

A continuación un extracto del artículo de Wikipedia dónde me he encontrado  con esta clase  por primera vez. Muchos nombres conocidos…

László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson showed that unless EXPTIME collapses to MA, BPP is contained in[9]

{\mathbf {i.o.-SUBEXP}}=\bigcap \nolimits _{{\varepsilon >0}}{\mathbf {i.o.-DTIME}}\left(2^{{n^{\varepsilon }}}\right).

The class i.o.-SUBEXP, which stands for infinitely often SUBEXP, contains problems which have sub-exponential timealgorithms for infinitely many input sizes.

P.s. ¿ Que diferencia hay entre un algoritmo de complejidad exponencial (por ejemplo 2^n^2) y un algoritmo de complejidad subexponencial (por ejemplo 2^Raiz cuadrada[n logn] ?. A escala, la misma que entre un algoritmo cuadrático y otro subcuadrático.

¿ Y es esto importante en la práctica ?. Dejemos  que hablen otros  por nosotros: The Fast Fourier Transform (FFT) of Cooley and Tukey [34] reduced the cost of doing Fourier transforms from the naive O(n 2 ) down to O(n log n), allowing a large class of problems to be attacked by computers. Mikhail Atallah7 remarked the FFT is the most important algorithm in computer science. The success of the FFT is that so many other problems can be reduced to a Fourier transform, from multiplication of numbers and polynomials to image processing to sound analysis to correlation and convolution 8 . More references are Beth[19], Karpovsky[72], and Maslen and Rockmore [93]. 

Por supuesto lo que le da relevancia a FFT no es solo que se haya conseguido acelerar el proceso, sino la cantidad de aplicaciones que este tenía, previamente a la aceleración. Aceleración sin aplicaciones es puro deporte.

Anuncios

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: