Formal Methods 101: Complexity Theory

Introduction:

  • Complexity Theory deals with how ‘complex’ a problem is to solve. That is, how many steps it takes to solve a problem.
  • This topic is one of the most profound and consequential topics in all of computer science and mathematics.

Big-O Notation:

  • Big-O notation is a notation that computer scientists use to describe the complexity of algorithms. This notation helps to describe how many steps an algorithm will take to complete a task at runtime.
  • Big-O notation attempts to capture these algorithms “scale” (i.e. their growth rate) as the problem sizes growth.
  • Types:
    • O(1) – Constant
    • O(n) – Linear
    • O(log(n)) – Logarithmic
    • O(n2) – Quadratic
    • O(n3) – Cubic
    • O(n^c) – Polynomial, C is a constant
    • O(c^n) – Exponential , C is a constant
    • O(n!) – Factorial

Example O(1):

  • function foo(int x):
    • x = x + 1 (step 1)
    • return x
  • The function ‘foo’ has Big-O of O(1) runtime, since no matter how big the input x is, it always takes the same number of steps (or amount of time) to compute things.

Example O(1):

  • function foo(int x):
    • x = x + 1 (step 1)
    • y = x + 1 (step 2)
    • z = x + 1 (step 3)
    • return x
  • The function ‘foo’ has Big-O of O(1) runtime, since no matter how big the input x is, it always takes the same number of steps (or amount of time) to compute things.
  • Note: Even though this is technically O(3) runtime, this is also equivalent to O(1) runtime. This is because O(1) and O(3) both have an equivalent growth rate; that is constant. Therefore, we usually just say this function has a O(1) runtime. (i.e. O(3) = O(1) = O(C), where C is a constant Integer).
  • Notice how this would still be a constant runtime even if we add more arbitrary steps because the number of steps does not increase based on the input size.

Example O(n):

  • function foo(int x):
    • y = 1 (step 1)
    • For 1 to size_of(x):
    • y = y + 1 (steps 2 to n+1)
    • return y
  • The function ‘foo’ has a Big-O of O(n) runtime, because depending on how big the input x is, the number of steps (or amount of time) to compute things will scale linearly with x.
  • Note: Even though this is technically O(n + 1) runtime, this is also equivalent to O(n) runtime. This is because O(n+1) and O(n) both have an equivalent growth rate; that is linear. Therefore, we usually just say this function has a O(n) runtime. (i.e. O(n+1) = O(n) = O(n + C), where C is a constant Integer).

Example O(n):

  • function foo(int x):
    • y = 1 (step 1)
    • z = 1 (step 2)
    • For 1 to size_of(x):
    • y = y + 1 (step 3 to n+2)
    • For 1 to size_of(x):
    • z = z + 1 (step n+3 to 2n+2)
    • return y, z
  • The function ‘foo’ has a Big-O of O(n) runtime, because depending on how big the input x is, the number of steps (or amount of time) to compute things will scale linearly with x.
  • Note: Even though this is technically O(2n+2) runtime, this is also equivalent to O(n) runtime. This is because O(2n+2) and O(n) both have an equivalent growth rate; that is constant. Therefore, we usually just say this function has a O(n) runtime. (i.e. O(2n+2) = O(n) = O(Bn+C), where B & C is are constant integers).
  • Notice how this would still be a linear runtime even if we add more non-nested for loops because the number of steps does not increase based on the input size.

Example O(n^2):

  • function foo(int x):
    • y = 1 (step 1)
    • For 1 to size_of(x):
      • For 1 to size_of(x):
        • y = y + 1 (steps 2 to n^2+1)
    • return y
  • The function ‘foo’ has a Big-O of O(n^2) runtime, because depending on how big the input x is, the number of steps (or amount of time) to compute things is will scale quadradically with x.

Example O(n ^ 3):

  • function foo(int x):
    • y = 1 (step 1) (step 1)
    • For 1 to size_of(x):
      • For 1 to size_of(x):
        • For 1 to size_of(x):
          • y = y + 1 (steps 2 to n^3+1)
    • return y
  • The function ‘foo’ has a Big-O of O(n^3) runtime, because depending on how big the input x is, the number of steps (or amount of time) to compute things is will scale cubically with x.

Example O(n^c):

  • function foo(int x):
    • y = 1 (step 1) (step 1)
    • For 1 to size_of(x):
      • For 1 to size_of(x):
        • For 1 to size_of(x):
          • ……
            • …….
              • ….…….
                • y = y + 1 (steps 2 to n^c+1)
    • return y
  • The function ‘foo’ has a Big-O of O(n^c) runtime, because depending on how big the input x is, the number of steps (or amount of time) to compute things is will scale to the power of c with x.

Complexity Classes:

  • In general, algorithms that have a polynomial runtime or lower are considered computationally friendly, and can be solved in a reasonable amount of time by a computer due to scaling polynomially. The class of problems that can be solved by deterministic polynomial runtime algorithms are known as the P-class problems. In other words, they are Polynomial-time problems that belong to the polynomial-time complexity class.
  • In contrast, algorithms that have an exponential runtime, prove to be very computationally challenging for computers as they scale. Computers often cannot solve these in a reasonable amount of time because they scale exponentially. This class of problems that required algorithms with exponential or greater runtimes are known as NP-hard class problems. Here, NP stands for Nondeterministic Polynomial-Time Problems. This essentially means that if we could search all paths of the problem at one time (simultaneously), we could find a polynomial-time solution.
  • NP-Complete class problems are a subclass of NP-Hard problems and a subclass of NP problems (however: NP class ≠ NP-Hard class) for which it is difficult to find a solution (takes an exponential time algorithm) but if the solution is known, if can be verified in Polynomial-time (by a polynomial-time algorithm). The de facto NP-Complete problem is SAT. It is very easy to verify a solution once it’s given, but it is very hard to find a solution. NP-Complete problems are the hardest problems in the NP class. In fact, if a Polynomial-time algorithm is found (none have been found yet) to solve an NP-Complete problem, then all NP problems can be solved using it.
  • NP class problems sit in between P and NP-Complete class problems and are a class of problems that can be reduced to NP-Complete problems (such as a being converted to a SAT problem) by a polynomial-time algorithm.
  • coNP class problems are a subclass of NP-Hard problems which, rather than being easy to verify a solution, it is easy to exclude non-solutions. In other words, you can exclude non-solutions in polynomial time. The de facto coNP-Complete problem is UNSAT (proving that a Boolean formula is unsatisfiable).
  • coNP-Complete class problems are the hardest problem in coNP. coNP problems are both NP-hard and coNP.
  • Every once in a while we find an efficient polynomial time algorithm for a problem in NP, and realize that it is actually a P problem; we just never realized it.
  • This leads us to one of the biggest unsolved questions in all of computer science and mathematics is:
  • P = NP? Or P ≠ NP?
  • If P = NP, then all of the NP-Complete & coNP-Complete problems (including SAT/UNSAT) are really P problems, and many of the computational challenges we have today will disappear.
  • The general suspicion is that P ≠ NP, but no one has been able to prove it.

Leave a Reply

Your email address will not be published. Required fields are marked *