what we are concerned with here are two things, that becomes easier to explain as three things:
* the problem's class
* the algorithm.. or proof
* the size of the input
* the problem's class:
each problem has a corresponding class(i) determined by a universal set of rules based on current solving algorithms and how they react to different input
in a beautiful and approachable paper by richard karp titled: reducibility among combinatorial problems(ii); karp showed that the hardest problems, that seem unable to be solved in polynomial or subpolynomial time, called NP-Hard, are basically all the same problem viewed from different perspectives
karp develops reducibility, a process used to show that one can reduce any of his 21 chosen problems into any of the others through a specific tree of transformations he calls reductions
this set of problems that form the tree of reductions is called NP-Complete
i say it is approachable because this paper develops reducibility and as such lacks any assumption about the reader's previous knowledge
.
* the algorithm:
check out this chart(iii) that lists some time complexities, you will see polynomial,P, time about mid way through
polynomial time is 2^O(log n) or poly(n), that 'O()' syntax is something called big O, which is analogous to a sort of algorithmic measurement unit(iv) derived from number of necessary operations in relation to the size of the input
all algorithms before the polynomial time listing are sub polynomial time for any inputs and as such are classified as P
.
* the size of the input:
lots of np problems have algorithm solutions that can solve specific inputs in polynomial time
sometimes those inputs are small, or follow a specific pattern, but a general purpose algorithm, or a collection of specific algorithms that can be proved to cover all possible inputs, that runs in a reduced(v) complexity of polynomial or sub polynomial time is necessary to be classified P
one way to prove P=NP is to take one of karp's problems and develop an algorithm that satisfies the above stated requirements
once developed karp's reductions can be used on the algorithm to show that all NP-Complete problems are in P as well, therefore P=NP
.
(i) http://en.wikipedia.org/wiki/Complexity_class
(ii) http://www.cs.berkeley.edu/~luca/cs172/karp.pdf
(iii) http://en.wikipedia.org/wiki/Time_complexity#Table_of_common...
(iv) http://en.wikipedia.org/wiki/Big_O_notation
(v) https://justin.abrah.ms/computer-science/big-o-notation-expl...