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
Ooh this is actually a good question. The gets at some of the deepest concepts in maths and CS. Let’s take a complexity and computability theory tour to see why “brute force” wouldn’t work.
## Definitions
First, we need to define what an “algorithm” is. We’ll use the classic abstraction, the [Turing Machine](https://en.wikipedia.org/wiki/Turing_machine) (TM), because it allows us to talk about algorithms and computation precisely.
Second, let’s define our goal. Let’s take [SAT](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem), and look at every algorithm to see if it solves it in polynomial time. SAT is in the class of [NP-complete](https://en.wikipedia.org/wiki/NP-completeness) problems, which means if we can find an algorithm that solves it in polynomial time, there is a reduction that allows us to solve every other NP problem in polynomial time, which is sufficient to prove `P = NP`. Inversely, if it can be shown no such algorithm can exist for SAT, it would imply `P ≠ NP`.
## Trying All Algorithms
### Case 1: If `P = NP`
The set of all TMs (algorithms) is [countably](https://en.wikipedia.org/wiki/Countable_set) infinite (can be put into [one-to-one correspondence](https://en.wikipedia.org/wiki/Bijection) with the set of all strings, or all natural numbers, etc.), so can you try them all and hope eventually you reach one that works?
For any given TM, how do you know if it solves SAT in polynomial time? You need to generate a proof. And the set of all proofs is—you guessed it—infinite. So you generate all possible proofs, and for each, you check if it’s valid. This is an infinite process.
You might say, wait, this a countably infinite process: using [interleaving](https://en.wikipedia.org/wiki/Dovetailing_(computer_science)), I can enumerate all TMs `T` cross all proofs `Q`, and for each `(t, q) ∈ T×Q`, check if `q` proves the statement `t solves SAT in polynomial time`, and if `P = NP`, eventually I will zig-zag my way to a proof that is valid. Very clever, but hold onto that thought. I’ll do you one better. But first…
### Case 2: If `P ≠ NP`
What if `P ≠ NP`? Then bruteforce search will never work: you cannot get a finite proof by exhaustion for the statement “for all `(t, q) ∈ T×Q`, `q` does not prove the statement `t solves SAT in polynomial time`” by checking every case.
## Alt Approach: Trying All Proofs
You might think, ah, since the set of proofs is countably infinite, and proofs can be checked in a finite amount of time, why not enumerate all proofs, and check one by one if any of them prove the statement `P = NP` or if it instead proves the statement `P ≠ NP`? Surely that is a process that is guaranteed to eventually halt, because either `P = NP` or `P ≠ NP`, right?
### The Fatal Flaw: Incompleteness
Well, unfortunately, [Gödel’s first incompleteness theorem](https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#First_incompleteness_theorem) tells us it’s *possible* no such proof exists, in which case this process will not halt. You simply don’t know if the proof is just a few more tries away or if there truly will never be an end to the search.
### Practicality
Theory aside, brute force search is impractical. Even if you knew that one of statements `P = NP` or `P ≠ NP` was in the class of statements for which there does exist a proof (which we don’t), it *still* wouldn’t be practical to enumerate and check. How would you know if the proof will be found in the first googol tries or in the first TREE(3) tries? How do you know there’s enough entropy in the universe to hold such a string?
Latest Answers