Artificial Intelligence is a fancy term for smart computers. Any program that can learn from past experience, behave similarly to a human, or strategize is often referred to as AI. A program that follows a set algorithm is not typically called Artificial Intelligence – it may seem the machine is intelligent by multiplying 3215 by 17.34 almost instantly, but that isn’t enough to earn the AI designation.
Believe it or not, there are a ton of problems that cannot be solved algorithmically. Possibly the most common example is a traveling salesman. A salesman wants to travel to 5 specific cities and return home using the minimum amount of gas. This is simple with a small number of cities, but what if he wants to go to 100 cities? How about a million?
When I say that it can’t be solved algorithmically, I mean that you can’t layout steps to getting to the right solution and know that it is the right solution without checking every other answer. You can’t just say: take the shortest road, then the shortest one to a city you haven’t been before, repeat until you’ve been to every city and then go home! Nope, not that simple.
Instead you don’t know that you have the best route without calculating every possible route. Even worse, the difficulty of finding the solution grows exponentially with each city added. How many possible routes are there with 4 cities? 6. 5 cities? 24. 6 cities? 120. 7 cities? 840. Wow that starts to go up pretty fast …
As you may have figured out, P problems are ones that can be solved algorithmically, or in Polynomial Time. Here is one example:
Suppose we have a large group of students that we need to pair up to work on projects. We know which students are compatible with each other and we want to put them in compatible groups of two.
But adding a small twist to the problem turns it into Nondeterministic Polynomial-Time:
What if we wanted to make groups of three students with each pair of students in each group compatible (Partition into Triangles)? What if we wanted to find a large group of students all of whom are compatible with each other (Clique)? What if we wanted to sit students around a large round table with no incompatible students sitting next to each other (Hamiltonian Cycle)? What if we put the students into three groups so that each student is in the same group with only his or her compatibles (3-Coloring)?
As you can see from these examples, there are many different types of NP problems. Let’s take a look at the Partition into Triangles example. First, you will notice that it is extremely easy to verify that you have a right answer, whereas with the traveling salesman you had to compare the distance to all the other calculated distances. And, you probably don’t have to calculate every possible combination to find one that works. But you also don’t have a way to guarantee there is or isn’t a solution without checking every possibility. NP.
AI programs can get you to a pretty darn good solution quickly. It may not be the best solution, but it is pretty darn close and took way less calculation. Now can you see why airline flight aggregator results are so crappy? You want to fly from San Francisco to New York? How many possible flights are there with one stop? How long of a delay in between flights is acceptable in this calculation? And if that isn’t enough to consider, how about if you make two stops? This problem is NP – they better get to applying some Artificial Intelligence so we can get our cheap flights quickly!
- The looooong article that inspired this post and provided the above quotes.
- These types of problems are the reasons super computers are used for things such as protein folding.
- Of course airline flight aggregator websites do apply Artificial Intelligence. They are likely to utilize information about airport hubs – United might have a cheap flight to New York through Denver, Delta through Atlanta, etc. But the beauty about these problems is that they can always be made better. Better results, faster results, less processing required, less memory required, and more.
- NP-complete problems are ones that if you found a solution (efficient algorithm) to solve one, you would be able to solve all NP problems. All the above examples are NP-complete.
- Bonus question for you (not that there are any points for the rest of this). If you randomly place numbers on a sudoku board, what percent of the time will you have a valid solution? Feel free to use the internet …
Photo: Dawn Huczek
I love this kind of stuff. A few bits to add:
Polynomial time doesn’t mean that the problem is not hard. The traveling salesman problem is NP, but another similar sounding problem, which is to find the shortest route from A to B, is not NP, it is P. However, the algorithm is a bit clever, so if you aren’t clever then you will default to an NP searching algorithm.
Many times, just because you need to search through all the possibilities, does not make something NP. For example, to find the smallest number in a set of number is P.
Finally, in real life many software either use approximations, or heuristics, or non-deterministic (some aspect of randomness) to generate good solutions to NP problems. Or, if they need certain provability or guarantee, like that it will finish in a certain amount of time or come up with a solution of a certain quality, then they may change the definition to make it solvable by a P class algorithm they can analyze.
Hi Alex, thanks for reading.
You are right of course, I oversimplified things here – P problems can be incredibly complex. One of my clients is a Stanford PhD level algorithms professor who told me that some theorists can come up with algorithms that are so complex they are simply impossible to implement.
Maybe I’ll do a follow up post on the different approaches to finding solutions to NP problems.