¿Hay algún número trascendental computable conocido tal que su º dígito es computable en tiempo polinomial, pero no en ?
cc.complexity-theory
comp-number-theory
XL _A__Aquí_Aquí
fuente
fuente
Respuestas:
Aquí está la construcción de tal número. Puede discutir si esto significa que tal número es "conocido".
Tome cualquier función de a donde el 'th dígitos no es computable en tiempo. Dicha función existe, por ejemplo, mediante la técnica de diagonalización habitual. Interpretar como el 'th dígito decimal de algún número real . Ahora, para cada de la forma , , cambie los dígitos de en las posiciones a 's. El número resultante conserva evidentemente la propiedad que elf N {1,2,…,8} n O(n) f(n) n α n 22k k≥1 α n,n+1,…,3n 0 β n -ésimo dígito no es computable en tiempo, pero tiene una infinidad de muy buenas aproximaciones de números racionales, por ejemplo a fin , de la forma . Entonces, según el teorema de Roth, no puede ser algebraico. (No es racional porque tiene bloques arbitrariamente largos de activados por nonzeros en ambos lados).O(n) O(q−3) p/q β 0
fuente
Más generalmente, para cualquier constante , hay números trascendentales computables en el tiempo polinómico, pero no en el tiempo O ( n k ) .k≥1 O(nk)
Primero, según el teorema de la jerarquía de tiempo, existe un lenguaje no computable en el tiempo O ( 2 k n ) . Podemos suponer que L ⊆ { 0 , 1 } ∗ , y también podemos suponer que todas las cadenas w ∈ L tienen una longitud divisible por 3 .L0∈E O(2kn) L⊆{0,1}∗ w∈L 3
Segundo, que sea la versión unaria de L 0 . Para mayor claridad, para cualquier w ∈ { 0 , 1 } ∗ , deje N ( w ) denotar el número entero cuya representación binaria es 1 w , y ponga L 1 = { a N ( w ) : w ∈ L 0 } . Entonces L 1 ∈ P , pero L 1 no es computable en el tiempo OL1 L0 w∈{0,1}∗ N(w) 1w L1={aN(w):w∈L0} L1∈P L1 . Además, L 1 tiene la siguiente propiedad: para cualquier m , L 1 no contiene ninguna a n tal que 2 3 m + 1 ≤ n < 2 3 m + 3 .O(nk) L1 m L1 an 23m+1≤n<23m+3
Tercero, dejemos que (Asumo aquí que la pregunta es sobre calcular números en binario. Si no, el 2 anterior se puede reemplazar con cualquier base deseada, no importa).
Entonces es computable en tiempo polinómico, ya que podemos calcular sus primeros n bits comprobando si a , a 2 , ... , a n están en L 1 . Por la misma razón, no es computable en tiempo O ( n k ) , como el n bit-ésimo determina si un n ∈ L 1 .α n a,a2,…,an L1 O(nk) n an∈L1
Para cualquier , supongamos que p = ∑ { 2 2 3 m + 1 - n : n ∈ L 1 , n < 2 3 m + 1 } = ⌊ α 2 2 3 m + 1 ⌋ , y q = 2 2 3 m + 1 . Entonces | α - pm
fuente