BROADCASTS.com

b'

Algorithms with similar runtimes are said to be in the same complexity class. That runtime is measured in the how many steps an algorithm takes relative to the input size.

The class P contains all algorithms which run in polynomial time (basically, a nested for loop iterating over the input).\\xa0 NP are algorithms which seem to require brute force.\\xa0 Brute force search cannot be done in polynomial time, so it seems that problems in NP are more difficult than problems in P.\\xa0 I say it "seems" this way because, while most people believe it to be true, it has not been proven.\\xa0 This is the famous P vs. NP conjecture.\\xa0 It will be discussed in more detail in a future episode.

Given a solution to a particular problem, if it can be verified/checked in polynomial time, that problem might be in NP.\\xa0 If someone hands you a completed Sudoku puzzle, it\'s not difficult to see if they made any mistakes.\\xa0 The effort of developing the solution to the Sudoku game seems to be intrinsically more difficult.\\xa0 In fact, as far as anyone knows, in the general case of all possible examples of the game, it seems no strategy can do better on average than just random guessing.

This notion of random guessing the solution is where the N in NP comes from:\\xa0Non-deterministic.\\xa0 Imagine a machine with a random input already written in its memory.\\xa0 Given enough such machines, one of them will have the right answer.\\xa0 If they all ran in parallel, one of them could verify it\'s input in polynomial time.\\xa0 This guess / provided input is often called a witness string.

NP is an important concept for many reasons.\\xa0 To me, the most reason to know about NP is a practical one.\\xa0 Depending on your goals or the goals of your employer, there are many challenging problems you may attempt to solve.\\xa0 If a problem you are trying to solve happens to be in NP, then you should consider the implications very carefully.\\xa0 Perhaps you\'ll be lucky and discover that your particular instance of the problem is easy.\\xa0 Sudoku is pretty easy if only 2 remaining squares need to be filled in.\\xa0 The traveling salesman problem is easy to solve if you live in a country where all roads for a ring with exactly one road in and out.

If the problem you wish to solve is not trivial, or if you will face many instances of the problem and expect some will not be trivial, then it\'s unlikely you\'ll be able to find the exact solution.\\xa0 Sure, maybe you can grab a bunch of commodity\\xa0servers and try to scale the heck out of your attempt.\\xa0 Depending on the problem you\'re solving, that might just work.\\xa0 If you can out-purchase your problem in computing power, then problems in NP will surrender to you.\\xa0 But if your input size ever grows, it\'s unlikely you\'ll be able to keep up.

If your problem is intractable in this way, all is not lost.\\xa0 You might be able to find an approximate solution to your problem.\\xa0 Good enough is better than no solution at all, right?\\xa0 Most of the time, probably.\\xa0 However, some tremendous work has also been done studying topics like this.\\xa0 Are there problems which are not even approximable in polynomial time?\\xa0 What approximation techniques work best?\\xa0 Alas, those answers lie elsewhere.

This episode avoids a discussion of a few key points in order to keep the material accessible.\\xa0 If you find this interesting, you should next familiarize yourself with the notions of NP-Complete, NP-Hard, and co-NP.\\xa0 These are topics we won\'t necessarily get to in future episodes.\\xa0 Michael Sipser\'s Introduction to the Theory of Computation is a good resource.

\\xa0