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
[removed]
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.
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?
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.
[removed]
P = NP is more of a conceptual problem than one we can just plug in and solve.
P is the set of problems that we can easily solve amd easily check the solutions. NP is the set of problems that we can easily check the solutions.
P = NP is the problem of does there exist a problem that exists in NP but not in P.
If we were to brute force the P = NP problem, we would first need to define every problem in NP (which itself is an impossible problem) and then we would need to find a simple solution to all of those problems. Even finding all of the solutions to a single NP problem (by brute force usually) takes an insane amount of time.
Latest Answers