LIPIcs.FSTTCS.2009.2336.pdf
- Filesize: 190 kB
- 10 pages
Document
Structure and Specification as Sources of Complexity
Author
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2009-12-14
Cite As Get BibTex
Anuj Dawar. Structure and Specification as Sources of Complexity. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 407-416, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2336
Abstract
If computational complexity is the study of what makes certain computational problems inherently difficult to solve, an important contribution of descriptive complexity in this regard is the separation it provides between the specification of a decision problem and the structure against which this specification is checked. The formalisation of these two aspects leads to tools for studying them as sources of complexity, and on the one hand leads to results in the characterisation of complexity classes and on the other elates to parameterized complexity. In these notes accompanying the invited talk, some definitions and results are presented leading to recent work on the characterisation of polynomial time and on the parameterized complexity of first-order logic on restricted graph classes.
Subject Classification
Keywords
- Computational Complexity
- Descriptive Complexity
- Logical Complexity
- Parametrized Complexity
- Locality
- Automata
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads