AIRCC's International Journal of Computer Science and Information Technology

Open Access Open Access  Restricted Access Subscription Access

On the Classification of NP Complete Problems and their Duality Feature


Affiliations
1 University of Electronic Science and Technology of China, Chengdu, China
 

NP Complete (abbreviated as NPC) problems, standing at the crux of deciding whether P=NP, are among hardest problems in computer science and other related areas. Through decades, NPC problems are treated as one class. Observing that NPC problems have different natures, it is unlikely that they will have the same complexity. Our intensive study shows that NPC problems are not all equivalent in computational complexity, and they can be further classified. We then show that the classification of NPC problems may depend on their natures, reduction methods, exact algorithms, and the boundary between P and NP. And a new perspective is provided: both P problems and NPC problems have the duality feature in terms of computational complexity of asymptotic efficiency of algorithms. We also discuss about the NPC problems in real-life and shine some lights on finding better solutions to NPC problems.

Keywords

P Problems, NP problems, NP Complete Problems,Reduction, The Duality Feature.
User
Notifications
Font Size

  • S.A. Cook (1971). The Complexity of Theorem Proving Procedures, Proceedings of the third annual ACM symposium on Theory of computing. pp. 151158, March of 1971.

  • R. M. Karp (1972), Reducibility Among Combinatorial Problems, In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85-103.

  • Clay Mathematics Institute, http://www.claymath.org/millennium-problems/millennium-prizeproblems.

  • Wikipedia, http://en.wikipedia.org/wiki/NP-complete.

  • W. I. Gasarch, (June 2002). The P=?NP poll , SIGACT News 33 (2): 34-47.

  • doi:10.1145/1052796.1052804. Retrieved 2008-12-29.

  • W. I. Gasarch, The Second P=?NP poll, SIGACT News 74, 2012.

  • Lance Fortnow, The Status of the P versus NP problem, Communications of the ACM. 52 (9): 78–86, 2009.

  • P vs NP website, http://www.win.tue.nl/gwoegi/P-versus-NP.htm

  • J. Kleinberg, E. Tardos, Algorithm Design, 2006, Pearson Education Asia Limited, pp. 475-479.

  • T. Cormen,C. Leiserson, R.L. Rivest,C. Stein, Introduction to Algorithm, 2nd edition, MIT Press, 2004.

  • G. J. Woeginger, Exact algorithms for NP-hard Problems: A Survey, Combinatorial optimization Eureka, you shrink! Pages 185 - 207 , Springer-Verlag New York, Inc. New York, NY, USA ©2003

  • M. Xiao, H. Nagamochi, Exact Algorithms for Maximum Independent Set, Algorithms and Computation, Volume 8283 of the series Lecture Notes in Computer Science pp 328-338.

  • R. Beigel and D.Epspstein, 3-coloring in time O(1.3446^n): A no MIS algorithm, Proceedings of the 36th Annual Symposium Foundations of Computer Science (FOCS'1995),444-453.

  • E. Dantsin, A. Goerdt, E.A. Hirsch, R. Kannan, J. Kleinberg, C.H. Papadimitriou, P. Raghavan, and U. Scho ̈ning, A deterministic (2 – 2/(k + 1))^n algorithm for k-SAT based on local search, Theoretical Computer Science 289 (2002) 69–83.

  • RE.Tarjan and AE. Trojanowski, Finding a maximum independent set, SIAM J. Comput.,vol.6, No.3, Sept. 1977.

  • J.W. Moon and L. Moser, On cliques in graphs. Israel Journal of Mathematics 3, 23–28,1965.

  • T. Jian, An O(2^(0.304n)) algorithm for solving maximum independent set problem. IEEE Transactions on Computers 35, 847–851,1986.

  • N. Bourgeois, B. Escoffier, V. T. Paschos, J. M. M. van Rooij, Fast algorithms for max independent set, Algorithmica 62(1-2), 2012.

  • W. Cook, In Pursuit of the Traveling Salesman, Princeton University Press, 2012.

  • O. Coudert, Exact Coloring of Real-Life Graphs Is Easy, in Proceedings of DAC '97 Proceedings of the 34th annual Design Automation Conference, Pages 121-126, Anaheim, California, USA — June 09 - 13, 1997

  • K. Helsgaun, General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation, 2009,doi: 10.1007/s12532-009-0004-6.

  • W. Tian, C. Huang, X. Wang, A Near Optimal Approach for Symmetric Traveling Salesman Problem in Eclidean Space, To appear in Proceedings of ICORES 2017, Portugal, also available at arxiv https://arxiv.org/pdf/1502.00447.pdf

  • L. Babai, Graph Isomorphism in Quasipolynomial Time, https://arxiv.org/abs/1512.03547, Dec 11, 2015.

  • A. Cho , Science news, mathematician-claims-breakthrough-complexity-theory, http://www.sciencemag.org/news/2015/11/mathematician-claims-breakthrough-complexity-theory, Nov. 11, 2015.

  • M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P, The Annals of Mathematics, Pages 781-793 from Volume 160, Issue 2, 2004.

  • F. L. Traversa, C. Ramella, F. Bonani and M.D. Ventra, memcomputing NP-complete problems in polynomial time using polynomial resources and collective states, Science, Vol. 1, no. 6, e1500031, Nov. 2015.


Abstract Views: 279

PDF Views: 141




  • On the Classification of NP Complete Problems and their Duality Feature

Abstract Views: 279  |  PDF Views: 141

Authors

Wenhong Tian
University of Electronic Science and Technology of China, Chengdu, China
Wenxia Guo
University of Electronic Science and Technology of China, Chengdu, China
Majun He
University of Electronic Science and Technology of China, Chengdu, China

Abstract


NP Complete (abbreviated as NPC) problems, standing at the crux of deciding whether P=NP, are among hardest problems in computer science and other related areas. Through decades, NPC problems are treated as one class. Observing that NPC problems have different natures, it is unlikely that they will have the same complexity. Our intensive study shows that NPC problems are not all equivalent in computational complexity, and they can be further classified. We then show that the classification of NPC problems may depend on their natures, reduction methods, exact algorithms, and the boundary between P and NP. And a new perspective is provided: both P problems and NPC problems have the duality feature in terms of computational complexity of asymptotic efficiency of algorithms. We also discuss about the NPC problems in real-life and shine some lights on finding better solutions to NPC problems.

Keywords


P Problems, NP problems, NP Complete Problems,Reduction, The Duality Feature.

References