Well its not proved so there is no theory, only conjecture. P is polynomial time algorithms, O(n^k) runtime for some k. Algorithms you can run on reasonable si

Well its not proved so there is no theory, only conjecture. P is polynomial time algorithms, O(n^k) runtime for some k. Algorithms you can run on reasonable sized inputs. NOT O(k^n) exponential time algorithms. Often a hard algorithm like finding the most efficient route through a city, can only be optimally solved by trying every combination of route. Thus, it's runtime is exponential in the number of inputs. However, if there existed a computer that could make lucky guesses, it could just guess the correct route and verify the answer. NP algorithms are Non-deterministic algorithms (guessers) that can solve harder problems in Polynomial time, like combinatorial problems. It is thought P != NP (for obvious reasons) but no-one can prove it. The philosophy of the conjecture is that some algorithms are fundamentally harder than others, but we can't prove it yet.