Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/22738

Turing's algorithmic lens: from computability to complexity theory
Díaz Cort, Josep; Torras, Carme
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. Institut de Robòtica i Informàtica Industrial; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals; Universitat Politècnica de Catalunya. ROBiri - Grup de Robòtica de l'IRI
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.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Automàtica i control
Automation
automation Author keywords: Turing
computer science
computability
complexity theory
algorithmics
Automàtica
Classificació INSPEC::Automation
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/publishedVersion
Artículo
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Díaz Cort, Josep; Dieter Wilhelm, Mitsche; Santi, Paolo
Díaz Cort, Josep; Lefteris, Kirousis; Mitsche, Dieter; Perez-Gimenez, Xavier
Álvarez Faura, M. del Carme; Díaz Cort, Josep; Petit Silvestre, Jordi; Rolim, José; Serna Iglesias, María José
Díaz Cort, Josep; Kaminski, Marcin; Thilikos Touloupas, Dimitrios
Díaz Cort, Josep; Dieter Wilhelm, Mitsche; Rustagi, Navin; Saia, Jared