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
Brute force only works if you have enough force.
Problems in the kind of field we’re talking about tend to have truly enormous search spaces. For example, consider the following problem:
* Is it possible to connect 45 dots with lines such that there is no set of 5 dots where either (a) none of the 5 are connected to any of the other 5 OR (b) *all* of the 5 are connected to *all* of the other 5?
The answer to this question is unknown. It’s known that it is possible to do so with 42 dots or less, and known that it is impossible with 48 or more, but the answer for 43, 44, 45, 46, and 47 is unknown.
We can’t even brute-force this relatively simple problem. Why? Because there are 45 * 44 / 2 = 990 possible connections between 45 vertices, and each can either be there or not, resulting in a search space of 2^990 possible connection schemes. 2^990 is a number with a little over 300 digits, which is far, FAR beyond anything you could brute-force.
To put some scale to it: if every proton in the (observable) Universe were its own Universe the size of our Universe, and every proton in *that* Universe itself were a Universe the size of our own, the number of protons in that third-order Universe of Universes of Universes would *still* be smaller than the number even for this relatively simple problem.
Or consider the problem just of writing a few lines of code. We can choose an *if* block, a *for* block, a *while* block, and then we can choose what to fill it with. Your search space, even for a simple function like the following:
def is_even(num):
if (num % 2 == 0):
return true
else:
return false
is well into the millions.
Latest Answers