Repeating Patterns in Linear Programs that express NP-Complete Problems - Computer Science > Computational ComplexityReport as inadecuate




Repeating Patterns in Linear Programs that express NP-Complete Problems - Computer Science > Computational Complexity - Download this document for free, or read online. Document in PDF available to download.

Abstract: One of my recent papers transforms an NP-Complete problem into the questionof whether or not a feasible real solution exists to some Linear Program. Theunique feature of this Linear Program is that though there is no explicit boundon the minimum required number of linear inequalities, which is most probablyexponential to the size of the NP-Complete problem, the Linear Program canstill be described efficiently. The reason for this efficient description isthat coefficients keep repeating in some pattern, even as the number ofinequalities is conveniently assumed to tend to Infinity. I discuss why thisconvenient assumption does not change the feasibility result of the LinearProgram. I conclude with two Conjectures, which might help to make an efficientdecision on the feasibility of this Linear Program.



Author: Deepak Ponvel Chermakani

Source: https://arxiv.org/







Related documents