2
$\begingroup$

I’m kind of a newbie to neural networks (and CS in general) but I was wondering if there are any methods to apply them in such a way with the aim of producing algorithms that solve difficult math problems.

A few CS/math friends were teaching me about P=NP and I was wondering whether a potential way to identify an algorithm that can convert the exponential time it takes to solve NP solutions into polynomial time is to use a genetic algorithm that applies brute-force until such an algorithm is identified.

Apologies if I’m misunderstanding anything or being too naive. Thank you for your time.

Improve this question
$\endgroup$
2
  • $\begingroup$ Here is a related question -- the second answer there lists various papers that have been written on using neural networks to solve NP-complete problems. It is very unlikely that they would be able to solve them in polynomial time, but they can be applied (as any other learning technique). $\endgroup$ – 6005 May 9 '20 at 1:58
  • $\begingroup$ By the way, there is a large research community that works on building efficient solvers for NP-complete problems (primarly SAT, as everything else reduces to that). They have a competition called the SAT competition and there are lots of successful solvers that work in practice, even though they don't work in polynomial time on all inputs. You might be interested to know that the best solvers, to my not entirely up-to-date knowledge, do not use machine learning techniques such as neural networks. But there are researchers who want to apply machine learning to see if they can do better. $\endgroup$ – 6005 May 9 '20 at 2:01
2
$\begingroup$

There are a few issues to consider.

If P!=NP, this approach is doomed from the start because you can't try every one of the infinite number of possible algorithms in finite time. That's I think the main deal-breaker here. Unless P=NP, which most people doubt, then the best you could ever do is say "my AI failed to find a polynomial-time algorithm in X amount of time", which doesn't mean no such algorithm exists. If you assume that P=NP, then in principle, an evolutionary algorithm, neural network, or other search technique could potentially find an example of a polynomial algorithm for an NP-complete problem, and that's all you need to prove that P=NP.

In practice, there are some challenges to deal with. I'm sure certain approaches would be more natural to try than others. Neural nets require numeric vectors of inputs and outputs, so you need to develop some way to encode an algorithm as a vector and a way to determine a binary "is_polynomial" so that you have an error gradient to follow. Or I suppose a continuous function measuring "degree of polynomial-ness" if such a thing makes sense. You're certainly going to need some way to measure success regardless of approach, but something like Genetic Programming could theoretically eliminate the need for a cumbersome translation of algorithm to real vector, since GP operates directly on an executable representation. Give it a Turing-complete set of operators to work with and it could presumably eventually find a polynomial solution if such a thing exists.

It's also far from clear that you have a friendly search space to work with here. I think most of the time, your hypothetical GP or whatever is going to wander around a very flat plateau of individuals that don't even successfully solve the problem, regardless of run-time. You could attempt to introduce a gradient to follow by favoring shorter programs or programs that terminate faster or whatever thing you came up with, but there's no good reason to think that gradient points in the direction of the prize-winning algorithm you're looking for. Theoretically, there are fairly easy conditions to meet that say given infinite search time, a given algorithm will eventually find any arbitrary solution that exists, but a workable algorithm in practice tends to require there be some structure in the search space that can be exploited. If you make a local move somewhere in the space that looks like it's better, you want that move to take you generally closer to the solution you're looking for. If the world looks basically random in terms of what moves me closer or further away, search algorithms struggle to do better than just randomly trying things.

Short answer, it's conceivably possible to build an algorithm that searches for poly-time solutions to an NP-hard problem, but the world is likely constructed so that that won't actually solve the problem you hope to solve.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Wow, thank you for the detailed answer. I am glad that someone took my thinking seriously. Could I follow up by asking whether you are aware of any publications that attempt to carry out something along these lines? It doesn’t have to be on the P=NP problem, but just any application of neural networks to create algorithms to solve difficult problems in maths. I would like to see the platform they did it on and see if I could at least try to attempt to execute your idea from there. $\endgroup$ – Garen May 8 '20 at 17:55
  • $\begingroup$ The closest thing I'm aware of is the field of automated theorem proving. It's not (as far as I know) particularly closely related to modern machine learning. But if this were an area I wanted to research, I'd probably start there and look for ways to apply something like neural nets or whatever to potentially improve some part of the process that's been developed there. $\endgroup$ – deong Jun 2 '20 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.