DEV Community

CodingBlocks

81. Understanding Complexity Theory

This episode we talk complexity theory while digging into Rob Conery’s The Imposter’s Handbook as Allen channels his inner Austin Powers, Michael finds linearly too complex to pronounce, and Joe ruins Batman for the rest of us.

Sponsors

Survey Says

During this episode we ask: How important is it that developers have an understanding of computer science-y topics?

How important is it that developers have an understanding of computer science-y topics?
  • Uh no.
  • Uh, yeah...I guess it's good.
  • It's not mission critical, but I prefer working with people who know their O from their Theta.
  • * Super important, and I can prove it mathmatically...if you accept my base case!
vote

News

  • Thank you to everyone that left us a review!
    • iTunes – N8__, 0321mike, the FQ, BearedWizzard, Traustitj
    • Stitcher – CodingBerserker, The Other Other Michael, Gabe Hodges, stunnedbysoup, izzmunkee, YuvalRaz, sov9, Mohamed Omran
  • Joe and Allen made some companion videos to episode 80
    • Develop ASP.NET Blazor Apps in a Docker Container – YouTube
    • Docker via Visual Studio for Dot Net Core – YouTube

Complexity Theory

There are multiple classifications:

P – polynomial

  • In math, polynomials employ only addition, subtraction, multiplication, and/or non-negative integer exponents operations.
  • These are simpler problems.
  • Most of the problems we are asked solve are not in P.
  • These scale linearly as the inputs scale.

NP – nondeterministic polynomial

  • Problems that are solvable in P time given a nondeterministic algorithm. – in the pub example, it was a “lucky guess” method.
  • A problem is classified as in NP time if can be:
    • Solved in exponential time
    • Verified in polynomial time
    • And solvable in P time by nondeterministic methods
  • These are the types of problems we enjoy, be it at code we write for work or games we play with friends.
  • These are the problems we deal with most on a daily basis. – also “enjoy” the most

NP-Complete

  • These are decision problems that are classifiable in both NP and NP-Hard.
  • These problems are the hardest problems in NP.

NP-Hard

  • These can be reduced to other problems in NP, but not all NP-Hard problems are within NP.
  • These problems are “at least as hard as the hardest problems in NP”.
  • These problems might not even be decidable.

Exp – exponentially complex, t=2^n

  • These are hard.
  • These problems do not scale well as the inputs are increased. On a graph, 2^n is a hockey stick.
  • These are the types of problems we’re _asked_ to solve.

 R

  • All problems that are solvable in finite time are said to be classified as in R.
    • P and Exp are solvable in finite time, therefore, they are also solvable in R.

And there are more classifications! But these are the ones we hear about most often.

  • Complexity theorists have found ways to reduce problems from one to another
  • There classifications help us to communicate how difficult something is.
    • This is part of _our_ ubiquitous language.
  • One of the goals of turning a complex problem into a decision problem is the ability to verify the answer.

_”…think about complexity in terms of time as you scale the inputs that go into the algorithm that you’re using to solve the problem.”_

  • Problems like the Halting Problem are beyond R.
    • The Halting Problem in summary – Write a generalized problem that can determine if any other program will finish running or continue infinitely.
    • The Halting Problem is considered undecidable.

_”Will we ever have the ability to solve problems nondeterministically?”_

  • Not yet, but some think we eventually will be able to, be it an algorithm or chip
  • But at the moment, NP!=P because we don’t have such an algorithm or chip
  • Prolog has the ability to pick one of a number of methods with the same signature and try them in a “guess” approach, with the ability to back-track

Karp’s 21 NP-Complete problems

Knapsack

  • A combinatorial optimization problem
  • _”Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.”_
  • Sounds perfect for a gameshow. Or a robbery. Any heist movie. Games. Scheduling.

Clique

  • Deals with graphs and graph theory
  • _”Consider a social network, where the graph’s vertices represent people, and the graph’s edges represent mutual acquaintance. Then a clique represents a subset of people who all know each other, and algorithms for finding cliques can be used to discover these groups of mutual friends.”_
  • Think Facebook.

Bin Packing

  • A variation of Knapsack, a combinatorial optimization problem
  • _”… objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used”_
  • Think UPS, FedEx, Amazon, any shipping service, airlines

Traveling Salesman

  • A combinatorial optimization problem
  • _”Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”_
  • Think Google Maps. Or election campaign tours. Think concert tours.

Approximations can sometimes solve these problems in P time.

  • Consider a map routing problem:
    • First, head to the nearest city.
    • From there, head to the next nearest city.
    • This approach is called the “nearest neighbor”.
      • This is a “greedy algorithm”. Meaning, you do what suits your needs at the current position and value on the graph.
      • Nearest neighbor is usually within 25% of the shortest path on average.

Summary

  • We can typically call simple, boring problems solvable in P time.
  • More difficult/complex problems, like group decisions, are solvable in exponential time (Exp).
  • Some problems are too complex to be determined in finite time, and are classified as undecidable.
    • Anything that can be solved, is solved in R.
    • P and Exp are subsets of R.
  • Within NP, we have subclasses of problems:
    • P – decision problems that can be solved deterministically in polynomial time.
    • NP – complex problems that can be solved in P time with nondeterministic methods.
      • These can be further broken down into:
        • NP-Complete – Decision problems we can easily/quickly verify.
        • NP-Hard – Can be reduced to other problems in NP, but not all NP-Hard problems are within NP.
  • We’re often asked to solve NP-Complete and NP-Hard problems.
  • Recognize them for what they are and approach them with care.

Resources We Like

Tip of the Week

Episode source