Title: Towards a Physical Oracle for the Partition Problem using Analogue Computing,
Abstract: Despite remarkable achievements in its practical tractability, the notorious
class of NP-complete problems has been escaping all attempts to find a
worst-case polynomial time-bound solution algorithms for any of them. The vast
majority of work relies on Turing machines or equivalent models, all of which
relate to digital computing. This raises the question of whether a computer
that is (partly) non-digital could offer a new door towards an efficient
solution. And indeed, the partition problem, which is another NP-complete
sibling of the famous Boolean satisfiability problem SAT, might be open to
efficient solutions using analogue computing. We investigate this hypothesis
here, providing experimental evidence that Partition, and in turn also SAT, may
become tractable on a combined digital and analogue computing machine. This
work provides mostly theoretical and based on simulations, and as such does not
exhibit a polynomial time algorithm to solve NP-complete problems. Instead, it
is intended as a pointer to new directions of research on special-purpose
computing architectures that may help handling the class NP efficiently.