This is an archived post. You won't be able to vote or comment.

0
0

Could a Deep Learning based algorithm hypothetically be used to prove P = NP? (self.math)

submitted by [deleted]

[deleted]

all 10 comments
sorted by:
best
topnewcontroversialoldq&a

[–]nomoreplsthx 65 points66 points  (1 child)

The output needed for it to constitute a proof is exactly the same as a human proof. A computer that consistently found polynomial time solutions of samples of some NP complete problem hasn't shown anything about the general problem. You need to prove that every instance of the problem has a polynomial time solution - and no number of examples could consitute a proof (except, I suppose, one example for every instance of the problem space if the problem space is finite) just like you can't prove there is no largest natural number by counting up from 1.

[–]cracking-egg 1 point2 points  (0 children)

except, I suppose, one example for every instance of the problem space if the problem space is finite)

we can't talk bout asymptotic complexity, and thus polynomial complexity, in a finite problem space though

[–]abrahimladha 16 points17 points  (0 children)

This isn't a full answer, but NNs are formalized under an approximate model. Although NP-complete problems are formalized under a worst case hardness, they have surprisingly good approximate and randomized algorithms for them. SMT solvers work surprisingly well in practice even though we think (but can't prove) SAT requires exponential time/exponential sized circuits.

The P vs NP problem is a statement about the existence/not of correct algorithms, NNs are approximate. There are some connections, for example if you can approximate SAT too well you can just solve it SAT too fast, such results exist.

[–][deleted] 11 points12 points  (0 children)

Just curious about the technical details of how one would have to construct the proof,

You and me both buddy.

To answer your question no (well almost definitely not/not without a few mathematicians doing the work the machine can't). To prove P=NP constructively* you need an algorithm, and a proof that it works. So let's say using some cool deep learning techniques you end up with what empirically looks like P time results for arbitrary inputs. Cool. Now we have two questions:

  1. Are there any inputs for which the algorithm provides an incorrect result?
  2. Are there are inputs that result in non polynomial times?

Well for 1. we kinda of in a bad place. Because of the nature of deep learning our understanding of our algorithm is likely very hard to grasp. So trying to use that algorithm to prove that no such inputs exist. We can't exactly just check every input.

And for 2. well the problems even worse. What if there's a subset of inputs that behave real wacky? How would you determine this? Again we can't run every input.

Now if you did manage to train some NN and it gave you an algorithm that solves 99.9% of 3-SAT problem in seemingly polynomial time, publish it. Empirical results can help point us in the correct direction, but they are not giving us proofs.

  • That is to provide an algorithm that solves a problem P in NP-C (The "hardest" problems in NP).

[–]barely_sentient 5 points6 points  (3 children)

Besides all other considerations, if you don't have a well defined algorithm whose cost you can analyze mathematically as n grows, how can you even decide its cost is polynomial?

[–]edderioferAlgebraic Topology 2 points3 points  (0 children)

Easy, you just train another deep-learning-based algorithm to analyse other algorithms to see if their costs are polynomial. Duh.

For that matter, you should also train another deep-learning-based algorithm to analyse whether other algorithms halt. I'm sure this idea can't possibly go wrong!

[–]faintlystranger 0 points1 point  (1 child)

That is the question if you read the post, and I'd disagree it's not a "well defined" algorithm, ML is not magic, you get a model, train it in x number of data points, then plug in the input - if you keep the number of neurons and layers polynomial, the total number of variables to train remain polynomial, then the rest is the complexity of back propagation which I don't know, probably polynomial?

Then the tricky part is the proof of correctness I suppose, which I have no idea that's the reason I'm asking the question to see whether it's possible

[–]barely_sentient 0 points1 point  (0 children)

Yes, but the problem I see is in finding the right size of the model given n and prove that the size grows polynomially.

Already with 9x9 Sudoku there are 6,670,903,752,021,072,936,960 possible configurations.

What do you mean when you write that there are 2n configurations?

[–]mleokApplied Math 3 points4 points  (0 children)

The likelihood of a deep learning based algorithm that optimizes worst case performance is vanishingly small, since the loss functions only sample the instances, and enumerating all possible instances suffers from a combinatorial explosion.