Definitions

• Computability: Is a certain task computable
• Complexity: If it is computable, is it solvable in a reasonable amount of time and memory?
  • YES: The task is efficiently computable
  • NO: The task is practically uncomputable
• Process: Another name for algorithm
• Task: Another name for problem

Representation

All tasks in computational complexity are represented as functions from $\{1,0{\}}^{\ast }\to \{1,0{\}}^{\ast }$

• We only consider functions that convert binary strings to binary strings.
• Other functions can be easily converted to such functions with Binary encoding of its input and/or output.

Languages

• A special case of tasks are whose which output a single bit: $\{1,0{\}}^{\ast }\to \{1,0\}$
• Also called:
  • Languages: This definition is similar to the definition of a language acceptor: a function that tells if a specific string is part of a certain language.
  • Characteristic functions: they say if a string has a certain characteristic (feature) or no.
  • Boolean functions
  • Decision tasks: They want to decide if a certain string is part of a language or has a certain characteristic.

Asymptotic Notation

The big O, big Omega and theta notations.