Computational complexity theory is the study of the analysis of the resources needed to solve computational problems. It focuses on the complexity class of problems solvable in the same amount of time and space.

Important complexity classes:

  • P (polynomial time) - The set of problems that can be solved in polynomial time.
  • NP (nondeterministic polynomial time) - The set of problems whose solutions can be verified in polynomial time.
  • NPC (NP-complete) - The hardest problems in NP. Showing that a problem is NP-complete provides evidence that the problem is computationally infeasible.

The most important unsolved question in computer science: Is P different from NP?

 

Computational models used in complexity theory:

  • Languages represent problems
  • Turing machines model algorithms
    • The deterministic Turing machine models computers
    • The nondeterministic Turing machine (such as the probabilistic Turing machine) helps classify the complexity of computational problems
    • The alternating Turing machine models parallel computation
  • The time and space required by a Turing machine is used to measure computational difficulty

 

Language terminology in computational problems:

  • The alphabet is a finite set of symbols.
  • A word is a finite sequence of symbols from the alphabet. 
  • The length of a word is the number of symbols in the word.
  • A language is a set of words.
  • A decision problem is a problem whose answer is YES or NO.
  • An optimization problem requires an algorithm to solve it.

 

Techniques used to prove relationships between classes:

  • Diagonalization - used in proofs of the Hierarchy Theorems
  • Padding argument

 

Important problems of computation theory:

  • Halting problem - An algorithm for this problem (if it exists) can be used to test if a program contains an infinite loop.
  • Universal computation problem - An attempt to design a universal algorithm which can simulate any other.
  • String compression - An important problem in information theory. It asks a question if the compression process can be automated.
  • Tiling - This problem found applications in architecture and crystallography.
  • Linear programming - This problem is important in economics, game theory, and operations research.

 

[Wiki] A finite automaton is an abstract machine that can be in one of a finite number of states. The machine can be only in one state at a time. The state it is in at any given time is called the current state. It can change from one state to another when initiated by a triggering event or condition; this is called a transition. A particular FSM is defined by a list of its states, and the triggering condition for each transition.

 

Applications of finite automata:

  • A logical model for the behaviour of neural systems.
  • Sequential circuit analysis.
  • A lexical analysis in text processing.
  • Asynchronous circuits.
  • Compiler design.
  • Computational biology.
  • Natural language processing.
  • Distributed computing.

 

References:

[1] Allen B. Tucker. "Computer Science Handbook, Second Edition". Chapman and Hall/CRC, 2 edition, 2004

[2] Sanjeev Arora and Boaz Barak. "Computational Complexity: A Modern Approach". Cambridge University Press

[3] Michael Sipser. "Introduction to the Theory of Computation". Cengage Learning