Programa

Complexidade Estrutural

Diploma de Estudos Avançados em Matemática

Programa

Complexidade de Kolmogorov: complexidade de Kolmogorov sem limite de recursos; complexidade de Kolmogorov com recursos limitados. Complexidade de prefixos. Teoria da informação algorítmica. Máquinas de Turing alternadas. Complexidade de circuitos uniformes: hierarquia NC; robustez. Isomorfismo e NP-completude: isomorfismos em tempo polinomial; cilindros polinomiais; conjuntos esparsos completos. Classes de complexidade não uniformes com conselhos em log, log*, poly e polylog: classes centrais P/poly, P/log* e BPP/log*. Algoritmos probabilísticos. Algoritmos estocásticos. Classes de complexidade. Computação com ruído. Hierarquia dos números reais de acordo com a sua incompressibilidade: hierarquia de Kolmogorov - de P(Q) a P/poly (R). A classe recursiva P. Computação experimental. Classes de complexidade que advêm da computação experimental em mecânica clássica e mecânica quântica. Aleatoriedade algorítmica. Classes de complexidade de problemas que se resolvem probabilística e estocasticamente recorrendo a sequências aleatórias.