Book contents
- Frontmatter
- Contents
- Preface
- List of Participants
- CLASSICAL RECURSION THEORY
- GENERALISATIONS
- APPLICATIONS
- Computing in Algebraic Systems
- Applications of Classical Recursion Theory to Computer Science
- “Natural” Programming Languages and Complexity Measures for Subrecursive Programming Languages: An Abstract Approach
Complexity Theory with Emphasis on the Complexity of Logical Theories
Published online by Cambridge University Press: 09 February 2010
- Frontmatter
- Contents
- Preface
- List of Participants
- CLASSICAL RECURSION THEORY
- GENERALISATIONS
- APPLICATIONS
- Computing in Algebraic Systems
- Applications of Classical Recursion Theory to Computer Science
- “Natural” Programming Languages and Complexity Measures for Subrecursive Programming Languages: An Abstract Approach
Summary
LECTURE 1. BASIC COMPLEXITY THEORY
Motivation
Complexity theory, at least as understood by computer scientists, is the study of the intrinsic difficulty of solving problems on a computer. In this series of lectures we attempt to give an advanced course in complexity theory with emphasis on some mathematical abstractions of computation such as nondeterminism, alternation and pushdown stores and their application to the understanding of the computational complexity of some logical theories. This course is not intended to be a survey of all that is known about the complexity of logical theories, but is instead intended to provide a student of the subject with some of the key ideas and methods so that he or she can pursue the subject further.
To clarify our definition of complexity theory we need to be more precise about what we mean by “problem”, “solving a problem”, “intrinsic difficulty” and “computer”.
Let Σ be a finite character set with at least two characters in it. The set Σ* represents the set of finite length strings in the alphabet Σ. If x µ Σ* then |x| is the length of x. Members of Σ* represent potential inputs or outputs of a computer program. A problem is a function from Σ* into Σ*. A 0–1 problem is a function from Σ* → {0, 1}. A 0–1 problem is commonly defined by a set, namely the set of strings whose image is 1 under the mapping. To solve a problem means to construct a computer program which has the same input/output behavior as the function defining the problem.
- Type
- Chapter
- Information
- Recursion Theory, its Generalisations and Applications , pp. 286 - 319Publisher: Cambridge University PressPrint publication year: 1980