A review of "Mem-computing NP-complete problems in polynomial time using polynomial resources" (arXiv:1411.4798)
This is an incremental critique addressing a flawed claim about solving NP-complete problems, relevant to computational complexity and hardware researchers.
The paper reviews a claim that an analog device solves the Subset Sum Problem in polynomial time and space, but the review points out flaws in the analysis and shows that scaling requires exponential resources.
The reviewed paper describes an analog device that empirically solves small instances of the NP-complete Subset Sum Problem (SSP). The authors claim that this device can solve the SSP in polynomial time using polynomial space, in principle, and observe no exponential scaling in resource requirements. We point out that (a) the properties ascribed by the authors to their device are insufficient to solve NP-complete problems in poly-time, (b) runtime analysis offered does not cover the spectral measurement step, (c) the overall technique requires exponentially increasing resources when scaled up because of the spectral measurement step.