Algorithms For Dummies

Considering NP complete problems

Usually you think of a greedy algorithm because other choices don’t compute the 

solution you need in a feasible time. The greedy approach suits problems for which 

you  have  many  choices  and  have  to  combine  them.  As  the  number  of  possible 

combinations  increases,  complexity  explodes  and  even  the  most  powerful 

---

CHAPTER 15

  Working with Greedy Algorithms 

     289

computer available fails to provide an answer in a reasonable time. For example, 

when attempting to solve a puzzle, you could try to solve it by determining all the 

possible ways you can fit the available pieces together. A more reasonable way is 

to start solving the problem by choosing a single location and then finding the 

best-fitting  piece  for  it.  Solving  the  puzzle  this  way  means  using  time  to  find 

the best fitting piece, but you don’t have to consider that location again, reducing 

the total number of pieces for each iteration.

Puzzle problems, in which the number of possible decisions can become huge, are 

more  frequent  than  you  expect.  Some  problems  of  this  type  have  already  been 

solved, but many others aren’t, and we can’t even transform them (yet) into ver-

sions  we  know  how  to  solve.  Until  someone  is  smart  enough  to  find  a  generic 

solution for these problems, a greedy approach may be the easiest way to approach 

them, provided that you accept that you won’t always be getting the best solution 

but a roughly acceptable one instead (in many cases).

These  difficult  problems  vary  in  characteristics  and  problem  domain.  Different 

examples of difficult problems are protein unfolding (which can help cure cancer) 

or breaking strong password encryption, such as the popular RSA cryptosystem 

(

http://blogs.ams.org/mathgradblog/2014/03/30/rsa/

).  In  the  1960s, 

researchers found a common pattern for all of them: They are all equally difficult 

to solve. This pattern is called the NP-completeness theory (NP stands for nonde-

terministic polynomial). In a sense, these problems distinguish themselves from 

others because it’s not yet possible to find a solution in a reasonable time —that 

is, in polynomial time.

Polynomial time means that an algorithm runs in powers of the number of inputs 

(known as P problems). Linear time is polynomial time because it runs O(n

1

). Also 

quadratic O(n

2

) and cubic O(n

3

) complexities are polynomial time, and though they 

grow quite fast, they don’t compare to NP-complete complexity, which is usually 

exponential time, that is, O(c

n

). Exponential time complexity makes it impossible to 

find a reasonable solution for any of these problems using brute force. In fact if n 

is large enough, you may easily have to try a number of solutions larger than the 

number of atoms present in the known universe. The hope of algorithm experts is 

that someone will find a way to solve any of these problems in the future, thus 

opening the door to solving all the NP-complete problems at one time. Solving 

NP-complete problems is one of the “Millennium Prize Problems” proposed by 

the  Clay  Mathematics  Institute,  which  offers  an  award  of  one  million  USD  to 

anyone  who  can  devise  a  solution  (

http://www.claymath.org/millennium- 

problems/p-vs-np-problem

).

NP is a broad class of algorithmic problems that comprises both P and NP-complete 

problems.  Generally,  NP  problems  are  difficult  (the  ones  that  require  you  to 

devise  a  smart  algorithm).  P  problems  are  solvable  in  polynomial  time; 

NP-complete  problems  are  so  hard  to  solve  that  the  associated  algorithms  run 

---

290