Podcast: Play in new window | Download

Subscribe: Apple Podcasts | Google Podcasts | Spotify | Stitcher | TuneIn | RSS

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

- Datadog.com/codingblocks – Sign up today for a free 14 day trial
get a free Datadog t-shirt after creating your first dashboard.*and* - Stack Overflow for Teams – Try it today with your first 14 days free.

## Survey Says

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

## 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

## Complexity Theory

- Complexity theory, aka computational complexity theory, focuses on classifying problems by difficulty

### 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.

- This is part of
- 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
- If so, then all NP problems get reduced to (or are solvable in) P time. Meaning NP=P.
- $1m if you can prove that P = NP (or vice verse)

- 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.

- These can be further broken down into:

- 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

- The Imposter’s Handbook – https://bigmachine.io/products/the-imposters-handbook
- Big-O Cheat Sheet – http://bigocheatsheet.com/
- Boolean satisfiability problem (SAT) (Wikipedia)
- Karp’s 21 NP-complete problems (Wikipedia)
- Computational complexity theory (Wikipedia)
- P (complexity) (Wikipedia)
- NP (complexity) (Wikipedia)
- NP-completeness (Wikipedia)
- NP-hardness (Wikipedia)

## Tip of the Week

- Temporal Tables in SQL Server 2016 – docs.microsoft.com
- Hacker Daily – https://hackerdaily.co/
- Learn This One Weird Trick To Debug CSS – https://medium.freecodecamp.org
- Right click on your API call, and select
*Replay XHR*in Chrome DevTools to recall that API. Makes testing server side changes super simple without needing to refresh your client. - Machine Learning made for .NET – http://dot.net/ml