Question

Aux pp. 7-8 de la complexité de calcul de Ker-I KO des fonctions réelles (1991), ce qui suit est indiqué dans des cas unidimensionnels:

Soit $ inv_1 $ l'opérateur qui mappe une fonction un à un $ f: [0,1] rightarrow [0,1] $ à sa fonction inverse $ f ^ {- 1} $. Alors $ inv_1 (f) $ est calculable en temps polynomial pour toutes les fonctions réelles en temps polynomial, un à un $ f $ sur $ [0,1] $.

Et pour les cas de deux dimensions:

Soit $ inv_2 $ l'opérateur qui mappe une fonction un à un $ f: [0,1] ^ 2 rightarrow [0,1] ^ 2 $ à sa fonction inverse $ f ^ {- 1} $. Alors $ p = np $ implique que pour tous les fonctions polynomiales calculables, les fonctions réelles un à un $ f $ sur $ [0,1] ^ 2 $, $ inv_2 (f) $ est calculable en temps polynomial, et cela à son tour implique $ p = up $.

Comment le cas unidimensionnel est-il dérivé? Et comment le cas bidimensionnel peut-il être étendu à N-dimensions?

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top