5
$\begingroup$

I'm sorry if the question is not relevant, i have tried to search for articles about it but i couldn't find satisfying answers.

I'm starting to learn about machine learning, neural networks etc ... and i was wondering if making a neural network that takes a graph as input, and output the answer of an np-complete problem (e.g. the graph is hamiltonian / the graph has independant set superior to k, and other decision problems) would work ?

I haven't heard of any np complete problems being solved like this, so i guess it does not work, are there theoretical results stating that a neural network cannot learn np-complete language or something like this ?

Improve this question
$\endgroup$
4
  • $\begingroup$ papers.nips.cc/paper/… found this online, hope it helps! $\endgroup$
    – nir shahar
    Commented Jul 9, 2020 at 19:07
  • 2
    $\begingroup$ It's certainly possible to train a neural network with the objective of solving an NP-hard problem. It's just not likely to always produce the right answer. $\endgroup$
    – Aaron Rotenberg
    Commented Jul 9, 2020 at 19:36
  • 4
    $\begingroup$ At the end of the day, neural network, after trained, is a usual algorithm running on a usual machine (it's essentially a sequence of matrix multiplications and activation function applications). Therefore, it is subject to the same constraints as other algorithms: if it's impossible to solve something in polynomial time, then neither can neural network do this in polynomial time. $\endgroup$
    – user114966
    Commented Jul 20, 2020 at 5:56
  • $\begingroup$ Neural Nets are good at interpolation, poor at extrapolation. You will spend a hard time feeding the net with sample solved problems. $\endgroup$
    – user16034
    Commented Jan 27, 2023 at 18:09

3 Answers 3

Reset to default
4
$\begingroup$

To answer your question, I would to point you to the field of computational learning theory (CLT), which applies complexity theoretic approaches to analyse machine learning.

An important concept in CLT is probably approximately correct (PAC) learning: in simple terms, a problem is PAC learnable if there exists an efficient algorithm which learns the data using a polynomial number of samples from the underlying distribution of the problem with an (polynomially small) error of $\epsilon$ and (polynomially small) failure probability $\delta$.

Unfortunately, there is a big disconnect between results in CLT and results in applied machine learning, so you are unlikely to find result proving or disproving the learnability of NP complete problems using deep neural networks as it is still an active area to research.

Here are some resources to computational learning theory:

https://www.cs.ox.ac.uk/people/varun.kanade/teaching/CLT-HT2018/lectures/lecture01.pdf

Section 3 defines and gradually introduces the concept of PAC learning

  • Section 5.1 of these notes show how 3-COLOURABILITY can be phrased in the PAC learning framework:
  • In Section 5 as well, the notes show how "3-TERM-DNF is not efficiently PAC learnable (take II) unless RP = NP"
Improve this answer
$\endgroup$
2
$\begingroup$

"Neural networks" are just regular (randomized) algorithms. The same restrictions apply: If $P \ne NP$, they won't be able to solve NP-complete problems in polynomial time either. They are attractive ways to find approximate solutions, but again, there are problems for which even getting a decent approximation is still (the analogue in search problems to the decision problems') NP-complete. Again, no way around that unless $P = NP$ (it which case the exercise is pointless anyway).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Correct me if I'm wrong, but after training, a neural network is a deterministic algorithm. Also, if we would like to talk about randomized algorithms, shouldn't we talk about $BPP$ class (or another one from this family) instead of $P$? $\endgroup$
    – user114966
    Commented Jul 20, 2020 at 17:51
-5
$\begingroup$

So it would be a PROOF that P=NP, isn't it? IMHO worth checking and researching... Big prize ahead! 😉

Improve this answer
$\endgroup$
1
  • $\begingroup$ Not at all. There are already plenty of heuristics solving NPC problems. $\endgroup$
    – Juho
    Commented May 20, 2023 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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