A Differential Approach for Several NP-hard Optimization Problems

In this paper, we study a variety of NP-hard optimization problems, such as MAXCUT, MAXkSAT, and MAXNAE2SAT from the perspective of obtaining exact solutions. We derive differentiable functions for each of these problems using the dataless neural networks framework. Recently, it was shown that a single differentiable function on a dataless neural network can capture the Maximum Independent Set problem. Inspired by this design, we design dataless neural networks for a host of combinatorial optimization problems. We also establish the correctness of our derivations in a rigorous fashion.