P versus NP: el problema estrella de la matemàtica de la computació

Authors

  • Elitza Maneva

Abstract

The problem ?P versus NP? is one of the seven Millennium Prize Problems of the Clay Mathematics Institute, whose solution would be awarded one million dollars. In this article we present in an informal manner the problem and its origin, giving along the way examples of computational problems of diferent levels of hardness, some non-trivial algorithms, the definition of Turing machine ? the mathematical model of a computer ? and the concept of polynomial reduction between problems. The most advanced part of the article presents a proof of Razborov?s 1985 theorem for monotone circuits, which solves a special case of the conjecture. We also give a translation into Catalan of a letter from Gödel to Von Neumann from 1956 which was discovered in 1988 and can be considered the first written formulation of the problem ?P versus NP?.

Downloads

Published

2012-07-12

How to Cite

Maneva, E. (2012). P <i>versus</i> NP: el problema estrella de la matemàtica de la computació. Butlletí De La Societat Catalana De Matemàtiques, 27(1), 39–62. Retrieved from https://revistes.iec.cat/index.php/BSCM/article/view/75930.001

Issue

Vol. 27 No. 1 (2012)

Section

Articles

License

The intellectual property of articles belongs to the respective authors.

On submitting articles for publication to the journal Butlletí de la Societat Catalana de Matemàtiques, authors accept the following terms:

  1. Authors assign to Societat Catalana de Matemàtiques (a subsidiary of Institut d’Estudis Catalans) the rights of reproduction, communication to the public and distribution of the articles submitted for publication to Butlletí de la Societat Catalana de Matemàtiques.
  2. Authors answer to Societat Catalana de Matemàtiques for the authorship and originality of submitted articles.
  3. Authors are responsible for obtaining permission for the reproduction of all graphic material included in articles.
  4. Societat Catalana de Matemàtiques declines all liability for the possible infringement of intellectual property rights by authors.
  5. The contents published in the journal, unless otherwise stated in the text or in the graphic material, are subject to a Creative Commons Attribution-NonCommercial-NoDerivs (by-nc-nd) 3.0 Spain licence, the complete text of which may be found at https://creativecommons.org/licenses/by-nc-nd/3.0/es/deed.en. Consequently, the general public is authorised to reproduce, distribute and communicate the work, provided that its authorship and the body publishing it are acknowledged, and that no commercial use and no derivative works are made of it.
  6. The journal Butlletí de la Societat Catalana de Matemàtiques is not responsible for the ideas and opinions expressed by the authors of the published articles.