Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Turing's algorithmic lens: from computability to complexity theory

Autor
Diaz, J.; Torras, C.
Tipus d'activitat
Article en revista
Revista
Arbor: ciencia pensamiento y cultura
Data de publicació
2013
Volum
189
Número
764
Pàgina inicial
1
Pàgina final
13
DOI
https://doi.org/10.3989/arbor.2013.764n6003 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/22738 Obrir en finestra nova
URL
http://dx.doi.org/10.3989/arbor.2013.764n6003 Obrir en finestra nova
Resum
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 ...
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.
Paraules clau
Automation Author Keywords: Turing, Computer Science, Computability, Complexity Theory, Algorithmics
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
ROBiri - Grup de Robòtica de l'IRI

Participants