Computing Partitions using Analog Circuits

In spite of remarkable achievements in computational power, the notorious class of NP-complete problems has escaped all attempts to find efficient algorithms for the worst-case instances. 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 (partially) non-digital computer could provide a new door to an efficient solution. Indeed, the partition problem, as one NP-complete sibling of the famous Boolean satisfiability problem, could be open to efficient solutions via analogue computing. This seed project shall explore the (physical) limits of computing set partitions by analogue computing. This shall help to get a better understanding of computational intractability (and the physical Church Turing hypothesis), by studying physical barriers, to which logical/digital counterparts may exist (e.g., such as pseudopolynomial complexity bounds, which, based on precursor results of the project, seem to exist in the physical and the digital realm). As such, the COMPAC project is a feasibility study to pave the way towards subsequent deeper studies of analog computing to possibly solve instances of problems that are intractable on digital computing architectures.