2
$\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 ?

$\endgroup$
3
  • $\begingroup$ papers.nips.cc/paper/… found this online, hope it helps! $\endgroup$ – nir shahar Jul 9 '20 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 Jul 9 '20 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$ – Dmitry Jul 20 '20 at 5:56
2
$\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"
$\endgroup$
0
$\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).

$\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$ – Dmitry Jul 20 '20 at 17:51

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.