viernes, 13 de agosto de 2010

La papiroflexia es NP-hard y otras curiosidades


Si pensabas que la papiroflexia era fácil, nada mas lejos de la realidad!

Unos investigadores han demostrado que la papiroflexia es un problema NP-hard. Sin entrar en complicaciones matemáticas, esto significa que, si bien es fácil comprobar que un esquema papiroflexico sobre el papel lleva a una figura concreta (i.e. doblandolo), es muy difícil encontrar una forma de doblar un papel para obtener una figura dada.

Lo hacen demostrando que es un problema equivalente al empaquetamiento de círculos, que ya se sabia anteriormente que era NP-hard. De regalo, han demostrado también que un numero cualquiera de círculos con área total 1 pueden ser empaquetados en un cuadrado de lado 8/pi.

Podéis ver el articulo aqui: http://arxiv.org/abs/1008.1224

Esta noticia me ha hecho mucha gracia, porque en muchos casos había oído que la matemática tiene en la papiroflexia mucho mas que un divertimento. Por ejemplo, con origami puedes resolver ecuaciones de segundo y tercer grado:
http://origami.ousaan.com/library/conste.html

Sistemas de ecuaciones diferenciales parciales:
http://cvgmt.sns.it/papers/dacmarpao10/

Y construcciones imposibles con regla y compás, como la triseccion del ángulo:
http://www.math.lsu.edu/~verrill/origami/trisect/