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

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

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.

Original language	English
Title of host publication	A Guided Tour of Artificial Intelligence Research
Subtitle of host publication	Volume III: Interfaces and Applications of Artificial Intelligence
Publisher	Springer International Publishing
Pages	51-89
Number of pages	39
Volume	3
ISBN (Electronic)	9783030061708
ISBN (Print)	9783030061692
DOIs	https://doi.org/10.1007/978-3-030-06170-8_2
Publication status	Published - 1 Jan 2020

Access to Document

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

Cite this

Bournez, O., Dowek, G., Gilleron, R., Grigorieff, S., Marion, J. Y., Perdrix, S., & Tison, S. (2020). Theoretical Computer Science: Computational Complexity. In A Guided Tour of Artificial Intelligence Research: Volume III: Interfaces and Applications of Artificial Intelligence (Vol. 3, pp. 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.

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

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

Abstract

Access to Document

Other files and links

Fingerprint

Cite this