Autor Tema: Decidir si una función es computable polinómicamente.

0 Usuarios y 1 Visitante están viendo este tema.

21 Septiembre, 2019, 11:45 am
Leído 480 veces

martiniano

  • Moderador Global
  • Mensajes: 1,285
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola, buenas.

Estoy haciendo un curso de autómatas y lenguajes formales en el que hay un tema llamado complejidad en tiempo cuya teoría me he mirado y más o menos entiendo pero en cuyos ejercicios me quedo bastante atascado. En general, no estoy seguro de por dónde van los tiros de lo que me piden. Empiezo con uno de ellos, que creo que prácticamente ya tengo, aunque con bastantes dudas. A ver qué os parece:

Di si la función \( f(n)=10^8log(n) \) es computable polinómicamente o no, y justifica la respuesta.

Para empezar, como ya he dicho, no estoy del todo seguro de haber interpretado bien el enunciado. Supongo que lo que me piden es decidir si se pueden sacar \( 8  \) cifras decimales del valor de \( log(n) \) en tiempo polinómico en el número de cifras de \( n \). Supongo también que \( n \) es un entero positivo. Suponiendo que es eso lo que me piden y basándome en cómo se calculaban hace unos años los logaritmos con las famosas tablas, contesto así:

Si llamamos \( k \) al número de cifras de \( n \) tenemos que:

\( log(n)=log(10^{k-1}\cdot{}10^{-(k-1)}\cdot{}n)=k-1+log(10^{-(k-1)}\cdot{}n) \)

Por lo que la parte entera de lo que me están pidiendo es \( k-1 \), valor que se puede sacar en tiempo polinómico en función de \( k \) y la parte decimal es \( log(10^{-(k-1)}\cdot{}n) \). Como \( 10^{-(k-1)}\cdot{}n\in{[1,10)}  \) entonces \( log(10^{-(k-1)}\cdot{}n)\in{[0,1)}  \)

Además, por las propiedades de la función logaritmo, para todo \( x_1,x_2\in{[1,10)} \) con \( x_2>x_1 \) tenemos que \( log(x_2)-log(x_1)<x_2-x_1 \). Por lo que si yo quiero un error menor que \( 10^{-8} \) al calcular \( log(x) \) con \( x\in{[1,10)} \), basta aproximar \( x \) con una precisión de \(  8 \) cifras decimales. Entonces basta que el algoritmo tenga calculados de antemano los logaritmos de \( (10-1)/10^{-8}=9\cdot{10^8} \) números diferentes. Por ser el conjunto de estos números un conjunto finito, buscar el que se necesita, que es aquel cuyas primeras cifras coinciden con todas las de \( n \), se puede hacer en un tiempo que no dependa del tamaño de \( x \), es decir, se puede acotar por una función constante. Y con ello todas las operaciones se hacen en tiempo polinómico y la función es computable polinómicamente.

No me acaba de convencer la forma. Tampoco estoy seguro de que mi razonamiento esté libre de errores ¿Tiene alguien alguna sugerencia, crítica, comentario io algo así?. Y también una curiosidad que tiene bastante que ver con esto, ¿alguien sabe cómo calculan las calculadoras los logaritmos? ¿utilizan lo de los desarrollos en serie de potencias, o tienen una "tabla de logaritmos"?

Muchas gracias de antemano por el tiempo y la ayuda. Un saludo.

21 Septiembre, 2019, 04:08 pm
Respuesta #1

geómetracat

  • Moderador Global
  • Mensajes: 1,905
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
A mí me parece todo correcto. ¿Qué es lo que nonte convence o no te gusta? Al fin y al cabo lo único que debes hacer es probar que existe un algoritmo que funciona en tiempo polinomial, y a mí me parece que el que describes funciona perfectamente.

Normalmente en temas de complejidad computacional se consideran funciones \( \Bbb N \to \Bbb N \). Se me ocurren dos interpretaciones para la función que te piden: la que usas tú (que imagino es a lo que se referían) o que sea \( 10^8 \) multiplicado por el valor del logaritmo, con lo cual el problema es trivial (cuentas el número de cifras del número y le añades ocho ceros).
La ecuación más bonita de las matemáticas: \( d^2=0 \)

21 Septiembre, 2019, 10:43 pm
Respuesta #2

martiniano

  • Moderador Global
  • Mensajes: 1,285
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola geómetracat. Muchas gracias por tu respuesta.

A mí me parece todo correcto. ¿Qué es lo que nonte convence o no te gusta?

Pues por un lado, siempre que plasmo una demostración me preocupa que no quede comprensible. Concretamente para la parte de aquí abajo he probado con varios párrafos antes de quedarme con éste:

Además, por las propiedades de la función logaritmo, para todo \( x_1,x_2\in{[1,10)} \) con \( x_2>x_1 \) tenemos que \( log(x_2)-log(x_1)<x_2-x_1 \). Por lo que si yo quiero un error menor que \( 10^{-8} \) al calcular \( log(x) \) con \( x\in{[1,10)} \), basta aproximar \( x \) con una precisión de \(  8 \) cifras decimales. Entonces basta que el algoritmo tenga calculados de antemano los logaritmos de \( (10-1)/10^{-8}=9\cdot{10^8} \) números diferentes.

Pero bueno, si tú dices que se entiende bien me fío de tu criterio. ¡Estupendo!

Por otro lado, en el tema que nos ocupa, creo que tengo problemas con la complejidad de los algoritmos básicos. En plan sumas, restas, divisiones... Es que no he encontrado ningún material en el que se expliquen estas cosas. Si supieses de alguno, te agradecería que me facilitases alguna referencia. En la respuesta al ejercicio que nos ocupa, por ejemplo, de lo que no estaba nada seguro era de esto:

Por ser el conjunto de estos números un conjunto finito, buscar el que se necesita, que es aquel cuyas primeras cifras coinciden con todas las de \( n \), se puede hacer en un tiempo que no dependa del tamaño de \( x \), es decir, se puede acotar por una función constante.

Es posible que abra más hilos próximamente con problemas parecidos y con dudas sobre estos algoritmos básicos. Por otro lado, celebro poder confirmar esto:

Normalmente en temas de complejidad computacional se consideran funciones \( \Bbb N \to \Bbb N \).

Porque cuando en un principio me topé con este ejercicio estuve un rato con preguntas en mi cabeza del tipo: "¿\( \log(n) \), pero si eso será en general un número irracional? ¿Cómo puedo determinar algo así en tiempo polinómico?" Y finalmente se me ocurrió que me estaban pidiendo lo que comenté. Es que... no sé... el material del curso que estoy siguiendo me parece en general bastante bueno, pero en la teoría de este tema echo de menos ejemplos que tengan que ver con los ejercicios a resolver que la acompañan. Menos mal de la completísima ayuda que se brinda en este foro.

Muchas gracias, y hasta pronto.  ;)

22 Septiembre, 2019, 12:19 am
Respuesta #3

geómetracat

  • Moderador Global
  • Mensajes: 1,905
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Por otro lado, en el tema que nos ocupa, creo que tengo problemas con la complejidad de los algoritmos básicos. En plan sumas, restas, divisiones... Es que no he encontrado ningún material en el que se expliquen estas cosas. Si supieses de alguno, te agradecería que me facilitases alguna referencia.

Es un tema un tanto peliagudo. El problema es que la complejidad de las operaciones básicas depende de los detalles de la implementación que consideres. Pero de todas formas, esto no suele ser importante ya que se usa notación \( O \) precisamente para olvidarse de los detalles concretos. Más aún si lo que te interesa es únicamente si hay algoritmos en tiempo polinomial: puedes suponer sin ningún problema que cualquier operación aritmética típica la puedes hacer en tiempo polinomial.

Puedes encontrar la complejidad de varios algoritmos aritméticos aquí:
https://en.m.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations
Como curiosidad, en marzo de este año se encontró el primer algoritmo para calcular el producto de dos enteros en tiempo \( O(n \log n) \), así que es un campo donde todavía no está todo dicho. (Eso sí, el algoritmo no es nada práctico: la constante es tan grande que solo es más rápido que algoritmos más simples para números mayores que el número de átomos en el universo.)



Citar
En la respuesta al ejercicio que nos ocupa, por ejemplo, de lo que no estaba nada seguro era de esto:

Por ser el conjunto de estos números un conjunto finito, buscar el que se necesita, que es aquel cuyas primeras cifras coinciden con todas las de \( n \), se puede hacer en un tiempo que no dependa del tamaño de \( x \), es decir, se puede acotar por una función constante.



Eso está perfecto: la clave está en que no depende del input, así que la complejidad de buscar en una lista finita es una constante, que podrá ser enorme, pero constante al fin y al cabo.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

22 Septiembre, 2019, 10:49 am
Respuesta #4

martiniano

  • Moderador Global
  • Mensajes: 1,285
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Es un tema un tanto peliagudo. El problema es que la complejidad de las operaciones básicas depende de los detalles de la implementación que consideres. Pero de todas formas, esto no suele ser importante ya que se usa notación \( O \) precisamente para olvidarse de los detalles concretos. Más aún si lo que te interesa es únicamente si hay algoritmos en tiempo polinomial: puedes suponer sin ningún problema que cualquier operación aritmética típica la puedes hacer en tiempo polinomial.

Ya, yo pensaba eso, pero cuando se me planteó si la función \( f(n)=2^n \) era polinómicamente computable, me di cuenta de que no me podía confiar. En este caso, si no voy mal, tan sólo el número de cifras que se deben escribir no admite una cota polinómica en en tamaño de \( n \).

Puedes encontrar la complejidad de varios algoritmos aritméticos aquí:
https://en.m.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

Perfecto, esto es justo lo que me hacía falta.  :aplauso:

Como curiosidad, en marzo de este año se encontró el primer algoritmo para calcular el producto de dos enteros en tiempo \( O(n \log n) \), así que es un campo donde todavía no está todo dicho. (Eso sí, el algoritmo no es nada práctico: la constante es tan grande que solo es más rápido que algoritmos más simples para números mayores que el número de átomos en el universo.)

Pues sí, curioso y sorprendente. Siempre está bien estar actualizado.  ;)

Muchas gracias por todo, y un saludo.