En este trabajo se presenta una frontera entre la eficiencia e ineficiencia de problemas abstractos en un marco computacional inspirado en la estructura y funcionamiento de las c´elulas de los organismos vivos. M´as concretamente, se justifica que una regla de reescritura, abstracci´on de la mitosis celular, proporciona un l´ımite de la tratabilidad de problemas, bajo el supuesto de que se verifique la conjetura P 6= NP. Como consecuencia relevante se obtienen nuevas herramientas que permiten atacar la resoluci´on de la citada conjetura en un marco absolutamente novedoso.

Ministerio de Ciencia e Innovación TIN2009–13192

Junta de Andalucía P08–TIC-04200