1.Previous
3.Next

A standard method for demonstrating lower bounds for problem complexites consists of reducing a problem to another problem. More precisely, suppose that one may encode a problem of size into a subproblem of size of a problem , and that the complexity of is Without loss of generality, one may suppose that the function increases with and has an inverse function . Then the complexity of the problem is This is the method that is used to prove that, if P != NP (an

1.Previous
3.Next