Computer Science – Computational Complexity
Scientific paper
2010-03-05
Computer Science
Computational Complexity
4 Pages, 1 Generalization of earlier Theorem, and 2 Conjectures
Scientific paper
One of my recent papers transforms an NP-Complete problem into the question of whether or not a feasible real solution exists to some Linear Program. The unique feature of this Linear Program is that though there is no explicit bound on the minimum required number of linear inequalities, which is most probably exponential to the size of the NP-Complete problem, the Linear Program can still be described efficiently. The reason for this efficient description is that coefficients keep repeating in some pattern, even as the number of inequalities is conveniently assumed to tend to Infinity. I discuss why this convenient assumption does not change the feasibility result of the Linear Program. I conclude with two Conjectures, which might help to make an efficient decision on the feasibility of this Linear Program.
No associations
LandOfFree
Repeating Patterns in Linear Programs that express NP-Complete Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Repeating Patterns in Linear Programs that express NP-Complete Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Repeating Patterns in Linear Programs that express NP-Complete Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-686760