Palestra: Uma teoria de NP-completude e condicionamento para computações reais aproximadas

Palestrante: Gregorio Malajovich (IM-UFRJ)

Data: 04 de setembro 2019 (quarta-feira)
Horário: 10:10
Local: Sala C-119 - CT - UFRJ

Resumo: Em 1989, Blum Shub e Smale propuseram uma teoria da computação e de complexidade sobre um anel. Um dos objetivos era modelar computações numéricas, usando números reais. Esse modelo tem sido criticado por se distanciar da `prática’ numérica. Nesta palestra, apresento uma extensão da teoria envolvendo números de condicionamento e aritmética de ponto flutuante, mas conservando uma das características cruciais do modelo clássico: a existência de um problema NP-completo (Trabalho conjunto com Mike Shub).