O que quero deixar claro é o seguinte: muitos conceitos de teoria da complexidade computacional não são absolutos. Dependem do contexto formal, axiomático, dentro do qual estamos.
2011/9/29 Francisco Antonio Doria <[email protected]> > 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 > > -- fad ahhata alati, awienta Wilushati _______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
