I learned that we sometimes use computers to generate proofs and algorithms for tough problems humans have trouble solving. And ChatGPT seems to suggest one day AIs could generate algorithms.
Has anyone tried to bruteforce search and see if any algorithm solves P = NP, or is there a technical reason we can’t? Do we not have the computer power, or it would take too long? Or would the math be too hard?
It seems like a lot of money could be made and would solve one of the biggest computer problems ever, so could it be worth it if it’s doable? What stops us?
In: 1
Bruteforcing is exactly what P=NP is trying to avoid.
No one is saying that you can’t brute force complex problems to identify the solutions. There may be technical challenges involved (i.e. the problem is too complex to brute force in a reasonable amount of time) but brute force is theoretically possible for all complex problems.
P = NP is asking the question _can all problems with easily verifiable solutions also have easy ways to compute said solutions?_ I.e – is there a way to avoid brute force? All of modern cryptography is based on the idea that the answer to this question is **no** – some problems are incredibly complex to solve but very easy to verify a solution is correct. In other words P =/= NP and brute force is the only way to come up with solutions.
The problem is that we haven’t _proved_ that to be true – we just assume it is. The entire point of P = NP is to try to develop a proof either way – prove that they can or cannot be easily solved.
Latest Answers