Fácil funciones?

Question

Deje $f$ ser una analítica de la función, y supongamos que queremos calcular $f(x)$. La entrada consta de los dígitos de $x$ y la salida de un número racional aproximar $f(x)$. Una función de $f$ se llama fácil si hay un algoritmo que calcula el $f(x)$ con exactitud $2^{-n}$ el uso de $n^{1+o(1)}$ las operaciones aritméticas.

Es conocido que las funciones elementales como $e^x,\log x$ son de fácil.

Es conocido (comprobado) acerca de cualquier razonable de la función que es difícil (no es fácil)?

Para un algoritmo, usando la AGM, mostrando que $e^x$ es fácil, una referencia es D. Newman, Racional aproximación comparación rápida de los métodos informáticos, Conferencias sobre la aproximación y el valor de la distribución, pp 149.174, Sém. De matemáticas. Sup., 79, Prensas Univ. Montreal, Montreal, Que., 1982.

EDIT1: El mismo papel que contiene una prueba de que la multiplicación es fácil (multiplicación rápida), y si $f$ es fácil, a continuación, la función inversa es fácil (método de Newton).

EDIT2: entiendo que con nuestros conocimientos actuales, no podemos calcular la constante de Euler de manera eficiente. Pero no sé, una prueba de que esto es imposible.

Observación. Lo que más me interesa funciones analíticas, incluso "funciones especiales". Son todos ellos de fácil?

Answer 1

Cualquier (uniformemente) polinomio de tiempo computable función debe tener un polinomio módulo de (uniforme) de continuidad [Ker-I Ko 1991,Teorema 2.10]. La función de $0\lt x\mapsto1/\ln(e/x)$ está bien definida en [0;1] y (exponencial de tiempo) computable aún no tiene ningún polinomio módulo de continuidad en 0; véase el Ejemplo 1.12 en arXiv:1211.4974. No es analítica en 0, aunque...

Para consolidar la pregunta sobre 'simple' de los números reales (es decir, constante funciones, cmp. Norbert Müller respuesta) que no son computables dentro del polinomio espacio, digamos, confieren períodos en el Modelo de la Teoría y este artículo de la Tienda de campaña y Ziegler.

Answer 2

Si tenemos en cuenta la constante de funciones (trivialmente analítica...), entonces podríamos cambiar el original de la pregunta a: ¿hay "razonable" de los números reales que no son computables en cuadrática tiempo? Como hay un tiempo jerarquico teorema de los números reales (Norbert Th. Müller: Subpolynomial Complejidad Clases de Funciones Reales y los Números Reales. ICALP 1986: 284-293), existen números en qubic tiempo que no están en cuadrática del tiempo. Si los números son como "razonable", como $\pi$ o $e$, sin embargo, es otra cuestión...

Answer 3

Aquí hay un par de referencias pertinentes. Voy a tratar de encontrar uno que es específicamente acerca de las funciones exponenciales. Pero en general es un poco demasiado optimista esperar que la baja complejidad como $n^{1 + o(1)}$. Usted no puede esperar a ser más rápido que el de la multiplicación.

• Ker I-Ko, la teoría de la Complejidad de funciones reales. Birkhäuser, 1991.
• Klaus Weihrauch, complejidad Computacional en computables métrica de los espacios, de la Lógica Matemática Trimestral, Volumen 49, número 1, páginas 3 a 21 de enero de 2003