P means it is very easy (polynomial time) to find the correct answer
NP means it is very easy (polynomial time) to check whether a given answer is correct.
NP-Hard (problems at least as hard as any NP problem) can be checkable in polynomial time algorithmically, while heuristics can often allow for quick, relatively accurate guesses.
Combining the two will probably allow for solving in P time *most of the time* (based on what we see with humans)
That's true, and heuristics are often "good enough". But it really depends on what your bar for good-enough is. Some human endeavors have high bars and large values of N.
The point is you can use heuristics to get close, verify in polynomial time, then try again if it isn't the optimal question.
If your heuristics are good enough and allow for battleships-style guessing, this should let you solve NPC problems in polynomial time in most instances.
Solve as in reach the actual, optimal solution and know that you have the correct solution
You're half-correct. You can use heuristics to get close, and you can verify in polynomial time. But formally, those two facts are not enough. With that strategy, you need to make an exponential number of guesses to make expected progress.
Let's say you're trying to improve a traveling salesman problem. You use heuristics to generate 10 paths and check them, and get a best-result of 70 hours. Then you check 100 paths and get a best-result of 65 hours. You check 1000 and bring it down to 62 hours. The point is that your gains diminish, and you need to exponentially increase your heuristic-driven guessing to get better and better results.
(Of course this is not true if feeding the results of your earlier guesses in to your heuristics is very helpful, but even assuming no learning, just culling options, I don't think estimations get exponentially more expensive to get any progress - only the addition of all the chunks of progress together to get to optimal make it exponential. This is with hard-coded algorithms!)
A very important intuition pump is that you can solve non-P problems in P time on average, the problem is doing in worst case scenarios.
This means "guessing" algorithmically is highly effective already, there are just some RNG examples of these problems that are unlucky and can't be solved in P time.
NP-hard problems have an exponentially growing solution space relative to input space. For any NP-hard problem, there exist problem instances where an exponential number of solutions must be examined to guarantee finding the optimal solution.
Per Wikipedia:
While some NP-hard problems like the knapsack problem can be approximated within a multiplicative factor ε > 0 (producing solutions arbitrarily close to optimum), others are impossible to approximate within any constant, or even polynomial, factor unless P = NP.
A polynomial-time approximation scheme (PTAS) can produce a solution within a factor (1 + ε) of optimal, but the running time, while polynomial in problem size, can grow dramatically as ε shrinks - for example, O(n^(1/ε)).
Wikipedia is always a nice recap, but the discussion in complexity theory is dealing with guarantees for worst case scenarios, and hard-coded algorithmic search rather rather live heuristics-based guesses.
The discussion is in bounds and absolutes which makes everything much more expensive computationally.
Making an intelligent guess and verifying whether you guessed right is usually rather cheap, and most instances of hard problems are not quite so hard.
Of course, there will be times when the estimates are good enough, in which case a super intellifent being would just use them (or maybe try guess a couple times first)
P means it is very easy (polynomial time) to find the correct answer
NP means it is very easy (polynomial time) to check whether a given answer is correct.
NP-Hard (problems at least as hard as any NP problem) can be checkable in polynomial time algorithmically, while heuristics can often allow for quick, relatively accurate guesses.
Combining the two will probably allow for solving in P time *most of the time* (based on what we see with humans)
That's true, and heuristics are often "good enough". But it really depends on what your bar for good-enough is. Some human endeavors have high bars and large values of N.
The point is you can use heuristics to get close, verify in polynomial time, then try again if it isn't the optimal question.
If your heuristics are good enough and allow for battleships-style guessing, this should let you solve NPC problems in polynomial time in most instances.
Solve as in reach the actual, optimal solution and know that you have the correct solution
You're half-correct. You can use heuristics to get close, and you can verify in polynomial time. But formally, those two facts are not enough. With that strategy, you need to make an exponential number of guesses to make expected progress.
Let's say you're trying to improve a traveling salesman problem. You use heuristics to generate 10 paths and check them, and get a best-result of 70 hours. Then you check 100 paths and get a best-result of 65 hours. You check 1000 and bring it down to 62 hours. The point is that your gains diminish, and you need to exponentially increase your heuristic-driven guessing to get better and better results.
This is a really fascinating claim.
Why would this be true?
(Of course this is not true if feeding the results of your earlier guesses in to your heuristics is very helpful, but even assuming no learning, just culling options, I don't think estimations get exponentially more expensive to get any progress - only the addition of all the chunks of progress together to get to optimal make it exponential. This is with hard-coded algorithms!)
A very important intuition pump is that you can solve non-P problems in P time on average, the problem is doing in worst case scenarios.
This means "guessing" algorithmically is highly effective already, there are just some RNG examples of these problems that are unlucky and can't be solved in P time.
I recommend Wikipedia for a good overview of this topic: https://en.wikipedia.org/wiki/Approximation_algorithm
NP-hard problems have an exponentially growing solution space relative to input space. For any NP-hard problem, there exist problem instances where an exponential number of solutions must be examined to guarantee finding the optimal solution.
Per Wikipedia:
While some NP-hard problems like the knapsack problem can be approximated within a multiplicative factor ε > 0 (producing solutions arbitrarily close to optimum), others are impossible to approximate within any constant, or even polynomial, factor unless P = NP.
A polynomial-time approximation scheme (PTAS) can produce a solution within a factor (1 + ε) of optimal, but the running time, while polynomial in problem size, can grow dramatically as ε shrinks - for example, O(n^(1/ε)).
Wikipedia is always a nice recap, but the discussion in complexity theory is dealing with guarantees for worst case scenarios, and hard-coded algorithmic search rather rather live heuristics-based guesses.
The discussion is in bounds and absolutes which makes everything much more expensive computationally.
Making an intelligent guess and verifying whether you guessed right is usually rather cheap, and most instances of hard problems are not quite so hard.
Of course, there will be times when the estimates are good enough, in which case a super intellifent being would just use them (or maybe try guess a couple times first)