Dos aspectos centrales del proyecto en curso del CAETI, de creacion de un ambiente de desarrollo
de software basado en conceptos avanzados de modularizacion y sintesis de comportamiento, son
la correctitud y la eficiencia. En relación al primer aspecto, en artículos anteriores describimos la
verificación axiomática de programas. En este artículo nos enfocamos en la eficiencia, presentando
una serie de notas que cubren sucintamente temas relevantes de la complejidad computacional,
área de la teoría de la computación que estudia la dificultad inherente de los problemas. Se tratan
los paradigmas determinístico, probabilístico y cuántico, incluyendo elementos vinculados con la
criptografía, las pruebas y la desaleatorización de los algoritmos. El material integra los contenidos
de la asignatura Métodos Formales en la Ingeniería de Software, que se dicta en el Doctorado en
Informática de la Facultad de Tecnología Informática de la UAI.