Theoretical Computer Science: Computational Complexity

Olivier Bournez; Gilles Dowek; Rémi Gilleron; Serge Grigorieff; Jean Yves Marion; Simon Perdrix; Sophie Tison

doi:10.1007/978-3-030-06170-8_2

Theoretical Computer Science: Computational Complexity

Olivier Bournez
, Gilles Dowek
, Rémi Gilleron
, Serge Grigorieff
, Jean Yves Marion
, Simon Perdrix
, Sophie Tison

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Chapitre › Revue par des pairs

Résumé

How much time, space and/or hardware resource does require an algorithm? Such questions lead to surprising results: conceptual simplicity does not always go along with efficiency. Alot of quite natural questions remain open, e.g., the famous P =NP problem raised in 1970. The so elementary model of finite automata, adequately tailored to diverse data structures, proves to be a flexible and powerful tool in the subject whereas quantum computing opens astonishing perspectives. An elegant tool for proofs of lower bounds for time/space complexity is a totally different notion of complexity: Kolmogorov complexity which measures the information contents.

langue originale	Anglais
titre	A Guided Tour of Artificial Intelligence Research
Sous-titre	Volume III: Interfaces and Applications of Artificial Intelligence
Editeur	Springer International Publishing
Pages	51-89
Nombre de pages	39
Volume	3
ISBN (Electronique)	9783030061708
ISBN (imprimé)	9783030061692
Les DOIs	https://doi.org/10.1007/978-3-030-06170-8_2
état	Publié - 1 janv. 2020

Accès au document

10.1007/978-3-030-06170-8_2

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

Bournez, O., Dowek, G., Gilleron, R., Grigorieff, S., Marion, J. Y., Perdrix, S., & Tison, S. (2020). Theoretical Computer Science: Computational Complexity. Dans A Guided Tour of Artificial Intelligence Research: Volume III: Interfaces and Applications of Artificial Intelligence (Vol 3, p. 51-89). Springer International Publishing. https://doi.org/10.1007/978-3-030-06170-8_2

@inbook{c6a3c6cbe2444766972a08e0996f52d7,

title = "Theoretical Computer Science: Computational Complexity",

abstract = "How much time, space and/or hardware resource does require an algorithm? Such questions lead to surprising results: conceptual simplicity does not always go along with efficiency. Alot of quite natural questions remain open, e.g., the famous P =NP problem raised in 1970. The so elementary model of finite automata, adequately tailored to diverse data structures, proves to be a flexible and powerful tool in the subject whereas quantum computing opens astonishing perspectives. An elegant tool for proofs of lower bounds for time/space complexity is a totally different notion of complexity: Kolmogorov complexity which measures the information contents.",

author = "Olivier Bournez and Gilles Dowek and R{\'e}mi Gilleron and Serge Grigorieff and Marion, \{Jean Yves\} and Simon Perdrix and Sophie Tison",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020.",

year = "2020",

month = jan,

day = "1",

doi = "10.1007/978-3-030-06170-8\_2",

language = "English",

isbn = "9783030061692",

volume = "3",

pages = "51--89",

booktitle = "A Guided Tour of Artificial Intelligence Research",

publisher = "Springer International Publishing",

}

Theoretical Computer Science: Computational Complexity. / Bournez, Olivier; Dowek, Gilles; Gilleron, Rémi et al.
A Guided Tour of Artificial Intelligence Research: Volume III: Interfaces and Applications of Artificial Intelligence. Vol 3 Springer International Publishing, 2020. p. 51-89.

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Chapitre › Revue par des pairs

TY - CHAP

T1 - Theoretical Computer Science

T2 - Computational Complexity

AU - Bournez, Olivier

AU - Dowek, Gilles

AU - Gilleron, Rémi

AU - Grigorieff, Serge

AU - Marion, Jean Yves

AU - Perdrix, Simon

AU - Tison, Sophie

PY - 2020/1/1

Y1 - 2020/1/1

N2 - How much time, space and/or hardware resource does require an algorithm? Such questions lead to surprising results: conceptual simplicity does not always go along with efficiency. Alot of quite natural questions remain open, e.g., the famous P =NP problem raised in 1970. The so elementary model of finite automata, adequately tailored to diverse data structures, proves to be a flexible and powerful tool in the subject whereas quantum computing opens astonishing perspectives. An elegant tool for proofs of lower bounds for time/space complexity is a totally different notion of complexity: Kolmogorov complexity which measures the information contents.

AB - How much time, space and/or hardware resource does require an algorithm? Such questions lead to surprising results: conceptual simplicity does not always go along with efficiency. Alot of quite natural questions remain open, e.g., the famous P =NP problem raised in 1970. The so elementary model of finite automata, adequately tailored to diverse data structures, proves to be a flexible and powerful tool in the subject whereas quantum computing opens astonishing perspectives. An elegant tool for proofs of lower bounds for time/space complexity is a totally different notion of complexity: Kolmogorov complexity which measures the information contents.

UR - https://www.scopus.com/pages/publications/105008840549

U2 - 10.1007/978-3-030-06170-8_2

DO - 10.1007/978-3-030-06170-8_2

M3 - Chapter

AN - SCOPUS:105008840549

SN - 9783030061692

VL - 3

SP - 51

EP - 89

BT - A Guided Tour of Artificial Intelligence Research

PB - Springer International Publishing

ER -

Theoretical Computer Science: Computational Complexity

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation