NP complexities

As an extension to the work that I have completed in January for my last paper submission, I wish to show the problem itself is NP-hard. But first is first, I have to learn what this NP business is and analyse some proofs. So I am currently reading about NP problems. I borrowed a very old looking book by Johnson from the library that looks like it will be very useful. In the decomposition of my A matrix into B and C, we would like to show that the problem itself is NP-Hard. To do so would be very good because we can quit using algorithms to solve it and work on heuristics.

In order to show the problem is NP-Hard, there are two steps that need to be performed:

1. Show Problem X is NP
   
2. Reduce an existing NP-Complete problem to it.
   

Task 1 is often simple. To accomplish task two, an arbitrary instance of a NP-Complete problem needs to be transformed into an instance of X such that the answer in the NP-Complete problem is positive if and only if the answer to the corresponding X is positive.

This is where the Johnson book comes in, to find a problem to reduce.