Complexidade computacional (não a algorítmica) é algo que depende fortemente do sistema formal. Por exemplo, suponhamos que se está estudando uma determinada classe de recursos computacionais, p.e. alguma medida de espaço ou de tempo, para máquinas de Turing. ntão, para sistemas formais como PA ou ZF, existem famílias de máquinas assim bounded que o são, provadamente, num sistema, e têm a propriedade desejada indecidível noutro.
-- fad ahhata alati, awienta Wilushati _______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
