Computational Complexity Theory

  • subfield of theoretical computer science
  • primary goal "is to classify and compare the practical difficulty of solving problems about finite combinatorial objects" source
  • "Complexity helps determine the difficulty of a problem, often measured by how much time and space (memory) it takes to solve a particular problem. For example, some problems can be solved in polynomial amounts of time and others take exponential amounts of time, with respect to their input size." source
  • complexity theory proposes "a formal criterion for what it means for a mathematical problem to be feasibly decidable – i.e. that it can be solved by a conventional Turing machine in a number of steps which is proportional to a polynomial function of the size of its input. The class of problems with this property is known as P – or polynomial time... P can be formally shown to be distinct from certain other classes such as EXP – or exponential time...complexity class known as NP – or non-deterministic polynomial time – consisting of those problems which can be correctly decided by some computation of a non-deterministic Turing machine in a number of steps which is a polynomial function of the size of its input. A famous conjecture – often regarded as the most fundamental in all of theoretical computer science – states that P is also properly contained in NP – i.e. P⊊NP." source

Real World Implications

  • can be important to algorithm design and analysis
  • often described in big-O notation
  • knowing if an algorithm runs in polynomial time vs exponential time can tell us how efficient an algorithm is

Decision Problems

  • "Such a problem corresponds to a set X in which we wish to decide membership." source
  • "...problems that can be answered with a "yes" or a "no." For example, "is this number prime?", "does this graph have a hamiltonian path?""is there an assignment of variables to the equation such that a set of constraints are satisfied?"" source
  • famous problems: Travelling Salesperson Problem, 3SAT, minimum spanning tree problems, primality testing
  • can be simulated on computational models like Turing machines

Copyright © 2022