Autor Tema: Demostrar que una función es polinómicamente computable.

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

23 Septiembre, 2019, 01:34 pm
Leído 418 veces

martiniano

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

Aquí ando de nuevo con inseguridades sobre un ejercicio de complejidad computacional. Agradecería que confirmaseis que lo que he pensado está bien o que me indicaseis los errores. El enunciado dice así:

Sean \( f \) y \( g \) dos funciones computables en tiempo polinómico. Proporciona un programa polinómico para \( h(x)=2^{\left |{f(x)}\right |}\cdot{}2^{\left |{g(x)}\right |} \)

En el material que estoy siguiendo \( \left |{x}\right | \) significa número de cifras de \( x \). Creo que un programa correcto sería, básicamente, realizar los siguientes pasos:

1) Calcular \( f(x) \) i \( g(x) \).
2) Contar el número de cifras de \( f(x) \) y \( g(x) \)
3) Elevar \( 2 \) a sendos números de cifras, multiplicando \( 2 \) por sí mismo las veces que haga falta.
4) Multiplicar los resultados con el algoritmo de escuela elemental.

Veamos que efectivamente, es un programa polinómico:

1) Por el enunciado se puede hacer en tiempo polinómico.

2) Contar el número de cifras de \( n \) es claramente un algoritmo \( O(|n|) \). Al ser \( f(x) \) computable en tiempo polinómico, debe haber un polinomio \( p(|x|) \) que acote \( |f(x)| \) y contar las cifras de \( f(x) \) es de complejidad \( O\left(p\left(|x|\right)\right) \), polinómica en \( |x| \). Lo mismo para \( |g(x)| \).

3) Calcular \( 2^n \) es hacer \( n-1 \) multiplicaciones por \( 2 \). Al tener \( 2 \) un sólo dígito, cada multiplicación se puede hacer en un número de operaciones del orden del tamaño del número que estamos multiplicando, es decir, el algoritmo es de complejidad \( O(|2^1|+...+|2^{n-1}|)=O(log(2)+...+log(2^{n-1}))=O(1+...+n-1)=O\left(\displaystyle\frac{(n-1)n}{2}\right)=O(n^2) \). Por lo que calcular \( 2^{|f(x)|} \) con este algoritmo es de complejidad \( O(|f(x)|^2)\subseteq{}O\left((p(|x|))^2\right) \), también polinómica en \( |x| \). Lo mismo para \( 2^{|g(x)|} \)

4) Sin pérdida de generalidad, asumo \( |2^{|f(x)|}|\geq{}|2^{|g(x)|}| \), entonces multiplicar ambos números mediante el algoritmo elemental es de complejidad \( O\left(\left(|2^{|f(x)|}|\right)^2\right)=O\left(\left(\log\left(2^{|f(x)|}\right)\right)^2\right)=O\left(|f(x)|^2\right)\subseteq{}O((p(|x|))^2) \), y la complejidad de este paso vuelve a ser polinómica.

El paso con el que más dudo es el 3). No he encontrado la complejidad de elevar un número a otro por ningún lado y me lo he inventado un poco. ¿Es correcto? Muchas gracias por vuestra ayuda y por vuestros comentarios. Un saludo.

23 Septiembre, 2019, 10:37 pm
Respuesta #1

geómetracat

  • Moderador Global
  • Mensajes: 1,905
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
La ecuación más bonita de las matemáticas: \( d^2=0 \)

24 Septiembre, 2019, 07:15 am
Respuesta #2

martiniano

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

Pues muchas gracias por mirártelo. Un saludo.