 |
 |
Algebra |
|
Authors: Deepak Ponvel Chermakani
We convert, within polynomial-time and sequential processing, an NP-Complete Problem into a real variable problem of minimizing a sum of Rational Linear Functions constrained by an Asymptotic-Linear-Program. The coefficients and constants in the real-variable problem are 0, 1, -1, K, or -K, where K is the time parameter that tends to positive infinity. The number of variables, constraints, and rational linear functions in the objective, of the real-variable problem is bounded by a polynomial function of the size of the NP-Complete Problem. The NP-Complete Problem has a feasible solution, if-and-only-if, the real-variable problem has a feasible optimal objective equal to zero. We thus show the strong NP-hardness of this real-variable optimization problem.
Comments: There are 6 Pages, 6 Theorems, 7 Figures. I also made a small correction that in Theorem-1, the correct word is "NP-Hard" and not "NP-Complete".
Download: PDF
[v1] 2012-12-20 04:53:25
[v2] 2012-12-21 04:13:24
Unique-IP document downloads: 367 times
Vixra.org is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. Vixra.org will not be responsible for any consequences of actions that result from any form of use of any documents on this website.
Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.
| Third-Party Links: |
|