Turing's algorithmic lens: from computability to complexity theory
10.3989/arbor.2013.764n6003
Inclou dades d'ús des de 2022
Cita com:
hdl:2117/22738
Tipus de documentArticle
Data publicació2013
Condicions d'accésAccés obert
Llevat que s'hi indiqui el contrari, els
continguts d'aquesta obra estan subjectes a la llicència de Creative Commons
:
Reconeixement-NoComercial-SenseObraDerivada 3.0 Espanya
Abstract
The decidability question, i.e., whether any mathematical statement could be computationally proven true or false, was raised by Hilbert and remained open until Turing answered it in the negative. Then, most efforts in theoretical computer science turned to complexity theory and the need to classify decidable problems according to their difficulty. Among others, the classes P (problems solvable in polynomial time) and NP (problems solvable in non-deterministic polynomial time) were defined, and one of the most challenging scientific quests of our days arose: whether P = NP. This still open question has implications not only in computer science, mathematics and physics, but also in biology, sociology and economics, and it can be seen as a direct consequence of Turing’s way of looking through the algorithmic lens at different disciplines to discover how pervasive computation is.
CitacióDiaz, J.; Torras, C. Turing's algorithmic lens: from computability to complexity theory. "Arbor (Madrid)", 2013, vol. 189, núm. 764, p. 1-13.
ISSN0210-1963
Versió de l'editorhttp://dx.doi.org/10.3989/arbor.2013.764n6003
Col·leccions
- ROBiri - Grup de Percepció i Manipulació Robotitzada de l'IRI - Articles de revista [163]
- Departament de Ciències de la Computació - Articles de revista [1.049]
- IRI - Institut de Robòtica i Informàtica Industrial, CSIC-UPC - Articles de revista [376]
- ALBCOM - Algorísmia, Bioinformàtica, Complexitat i Mètodes Formals - Articles de revista [274]
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
1491-Turing-s-a ... o-complexity-theory(1).pdf | 1014,Kb | Visualitza/Obre |