2019/02/10 by Diaby, Moustapha, Karwan, Mark H., Sun, Lei
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1902.03549
There has been a series of developments in the recent literature (by essentially a same "circle" of authors) with the absolute/unconditioned (implicit or explicit) claim that there exists no abstraction of an NP-Complete combinatorial optimization problem in which the defining combinatorial configurations (such as "tours" in the case of the traveling salesman problem (TSP) for example) can be modeled by a polynomial-sized system of linear constraints. The purpose of this paper is to provide general as well as specific refutations for these recent claims.