Computabilité en poly-temps de l'inversion des fonctions réelles poly-temps
-
31-10-2019 - |
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