2015/04/28 by Wenhong Tian, Tian, Wenhong, Guozhong Li +7
Engineering · Computer Science · #Scheduling and Optimization Algorithms #Optimization and Packing Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1505.00058
NP complete problem is one of the most challenging issues. The question of whether all problems in NP are also in P is generally considered one of the most important open questions in mathematics and theoretical computer science as it has far-reaching consequences to other problems in mathematics, computer science, biology, philosophy and cryptography. There are intensive research on proving `NP not equal to P' and `NP equals to P'. However, none of the `proved' results is commonly accepted by the research community up to now. In this paper, instead of proving either one, we aim to provide new perspective: transforming two typical NP complete problems to exactly solvable P problems in polynomial time. This approach helps to solve originally NP complete problems with practical applications. It may shine light on solving other NP complete problems in similar way.