What is P or NP, and why does it matter?
Within the field of Computer Science, an individual is presented with various problems to solve. Based upon the problem circumstances as well as the tools available to them, they might choose a number of potential different algorithms. They will hopefully choose an algorithm that can solve the problem effectively both as far as time complexity and space complexity. If for example we were to examine sorting an array, we might choose Insertion Sort if the array was reasonably already sorted or merge sort if the array could be considered completely unsorted. These are fine ways to solve a problem efficiently because an individual can trace out (via pen and paper) what will be the complexity of this approach even in the worst case.
But what about problems that cannot be solved so easily?
Before I dive deeper, I should elaborate on what perhaps makes something efficient in Computer Science.
The trend of giving Computers more and more processing power means that algorithms that were previously too costly can now be executed without worry. If for example we were to examine the Computers of the 1960s,
When given a multiplication problem between two integers: “a” and “b”,
Software Engineers were likely to simply add “a” to itself (“b” — 1) times; depending upon what “a” and “b”…
