NP Complete, An Introduction

Introduction

If a problem is np complete, it can be solved quickly by a nondeterministic computer, which only needs to verify its lucky guess; but the problem is exponentially difficult to solve on a deterministic machine, which has to try every possibility in search of an answer.

Consider the factorization of a large number n into two primes p and q. If you make a lucky guess, and you stumble upon p and q, it is easy to verify that p×q = n. It hardly takes any time at all, even if p and q are thousands of digits. However, if you don't know p and q, and you have to guess, you could be computing until our sun grows dim. This is the basis of rsa encryption, which is used to keep your electronic transactions secure.

Although this example is easy to understand, it isn't a very good example, because factoring may not be an np complete problem. (We haven't proven it to be in any case.) The classic example of an np complete problem is satisfiability, which attempts to "satisfy" a boolean expression by setting its inputs to true or false in just the right way. This is np complete because an algorithm that solves this problem solves all the other np problems, such as factoring, all in one go. You can almost see how this would work. Write p and q in binary, with boolean variables acting as the bits. Write a large boolean expression that implements p×q = n. Solve the boolean expression, and read p and q in binary, thereby factoring n. It's that easy.

Many other real-world problems would also be solved, if we could just solve satisfiability. That makes satisfiability an np complete problem.

A wide variety of problems, from various branches of mathematics, are np complete. Often the proof involves a reduction to satisfiability. Something like this.

Suppose there is an efficient algorithm to solve the green problem. Take an arbitrary boolean expression and convert it to an instance of the green problem. The conversion doesn't take too long, and the green problem isn't that much larger than the original boolean expression that created it. So - solve the green problem, and the boolean expression has also been solved. From here, all the other hard problems are solved, hence green is an np complete problem.

That's the idea; let's try it out in the real world.

Real World Mathematics of House Buying and Mortgage Calculation:
House Buying Math | Mortgage Calculator | Loan and Mortgage Math