So the problem has poor complexity: what next?

James H. Davenport

doi:10.1109/SYNASC61333.2023.00057

So the problem has poor complexity: what next?

University of Bath, Department of Computer Science

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

Abstract

Some interesting problems have a poor worst-case complexity, but may still be soluble in some, or many, cases. If appropriate, there is 'fixed-parameter tractability' as one way of describing the solubility. We can also look at weak complexity (i.e. ignoring rare bad cases, but in a principled way). But in other cases, e.g. SAT-solving, there isn't necessarily a neat theoretical solution, but powerful practical ideas. In particular, we look at computer algebra, and particularly real quantifier elimination.¹¹The author was partially supported by EPSRC grant EP/T015713.

Original language	English
Title of host publication	Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023
Editors	Sorin Stratulat, Mircea Marin, Viorel Negru, Daniela Zaharie
Place of Publication	U. S. A.
Publisher	IEEE
Pages	5-10
Number of pages	6
ISBN (Electronic)	9798350394122
ISBN (Print)	9798350394139
DOIs	https://doi.org/10.1109/SYNASC61333.2023.00057
Publication status	Published - 10 May 2024
Event	25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023 - Nancy, France Duration: 11 Sept 2023 → 14 Sept 2023

Publication series

Name	Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023

Conference

Conference	25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023
Country/Territory	France
City	Nancy
Period	11/09/23 → 14/09/23

Funding

The author was partially supported by EPSRC grant EP/T015713. He is grateful to the SYNASC 2023 organisers for inviting the talk that is the basis of this paper. He is grateful to Ali Uncu for his comments on the draft.

Funders	Funder number
Engineering and Physical Sciences Research Council	EP/T015713
Engineering and Physical Sciences Research Council

Keywords

complexity
computer algebra
real quantifier elimination

ASJC Scopus subject areas

Computational Theory and Mathematics
Computer Science Applications
Software
Numerical Analysis
Computational Mathematics
Health Informatics

Access to Document

10.1109/SYNASC61333.2023.00057

Cite this

Davenport, J. H. (2024). So the problem has poor complexity: what next? In S. Stratulat, M. Marin, V. Negru, & D. Zaharie (Eds.), Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023 (pp. 5-10). (Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023). IEEE. https://doi.org/10.1109/SYNASC61333.2023.00057

So the problem has poor complexity: what next? / Davenport, James H.
Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023. ed. / Sorin Stratulat; Mircea Marin; Viorel Negru; Daniela Zaharie. U. S. A.: IEEE, 2024. p. 5-10 (Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023).

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

Davenport, JH 2024, So the problem has poor complexity: what next? in S Stratulat, M Marin, V Negru & D Zaharie (eds), Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023. Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023, IEEE, U. S. A., pp. 5-10, 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023, Nancy, France, 11/09/23. https://doi.org/10.1109/SYNASC61333.2023.00057

Davenport JH. So the problem has poor complexity: what next? In Stratulat S, Marin M, Negru V, Zaharie D, editors, Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023. U. S. A.: IEEE. 2024. p. 5-10. (Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023). Epub 2024 May 10. doi: 10.1109/SYNASC61333.2023.00057

Davenport, James H. / So the problem has poor complexity : what next?. Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023. editor / Sorin Stratulat ; Mircea Marin ; Viorel Negru ; Daniela Zaharie. U. S. A. : IEEE, 2024. pp. 5-10 (Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023).

@inproceedings{932fd08646314c3eb37608a10eb210f5,

title = "So the problem has poor complexity: what next?",

abstract = "Some interesting problems have a poor worst-case complexity, but may still be soluble in some, or many, cases. If appropriate, there is 'fixed-parameter tractability' as one way of describing the solubility. We can also look at weak complexity (i.e. ignoring rare bad cases, but in a principled way). But in other cases, e.g. SAT-solving, there isn't necessarily a neat theoretical solution, but powerful practical ideas. In particular, we look at computer algebra, and particularly real quantifier elimination.11The author was partially supported by EPSRC grant EP/T015713.",

keywords = "complexity, computer algebra, real quantifier elimination",

author = "Davenport, \{James H.\}",

year = "2024",

month = may,

day = "10",

doi = "10.1109/SYNASC61333.2023.00057",

language = "English",

isbn = "9798350394139",

series = "Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023",

publisher = "IEEE",

pages = "5--10",

editor = "Sorin Stratulat and Mircea Marin and Viorel Negru and Daniela Zaharie",

booktitle = "Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023",

address = "USA United States",

note = "25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023 ; Conference date: 11-09-2023 Through 14-09-2023",

}

TY - GEN

T1 - So the problem has poor complexity

T2 - 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023

AU - Davenport, James H.

PY - 2024/5/10

Y1 - 2024/5/10

N2 - Some interesting problems have a poor worst-case complexity, but may still be soluble in some, or many, cases. If appropriate, there is 'fixed-parameter tractability' as one way of describing the solubility. We can also look at weak complexity (i.e. ignoring rare bad cases, but in a principled way). But in other cases, e.g. SAT-solving, there isn't necessarily a neat theoretical solution, but powerful practical ideas. In particular, we look at computer algebra, and particularly real quantifier elimination.11The author was partially supported by EPSRC grant EP/T015713.

AB - Some interesting problems have a poor worst-case complexity, but may still be soluble in some, or many, cases. If appropriate, there is 'fixed-parameter tractability' as one way of describing the solubility. We can also look at weak complexity (i.e. ignoring rare bad cases, but in a principled way). But in other cases, e.g. SAT-solving, there isn't necessarily a neat theoretical solution, but powerful practical ideas. In particular, we look at computer algebra, and particularly real quantifier elimination.11The author was partially supported by EPSRC grant EP/T015713.

KW - complexity

KW - computer algebra

KW - real quantifier elimination

UR - http://www.scopus.com/inward/record.url?scp=85193821989&partnerID=8YFLogxK

U2 - 10.1109/SYNASC61333.2023.00057

DO - 10.1109/SYNASC61333.2023.00057

M3 - Chapter in a published conference proceeding

AN - SCOPUS:85193821989

SN - 9798350394139

T3 - Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023

SP - 5

EP - 10

BT - Proceedings - 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2023

A2 - Stratulat, Sorin

A2 - Marin, Mircea

A2 - Negru, Viorel

A2 - Zaharie, Daniela

PB - IEEE

CY - U. S. A.

Y2 - 11 September 2023 through 14 September 2023

ER -

So the problem has poor complexity: what next?

Abstract

Publication series

Conference

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Pushing Back the Doubly-Exponential Wall of Cylindrical Algebraic Decomposition

Cite this

So the problem has poor complexity: what next?

Abstract

Publication series

Conference

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Projects

Pushing Back the Doubly-Exponential Wall of Cylindrical Algebraic Decomposition

Cite this