Review on Intractability
Krishnendu Basuli
Dr. Krishnendu Basuli*, Assistant Professor, Department of Computer Science, West Bengal University, Barasat, Kolkata (West Bengal), India.
Manuscript received on 04 May 2022. | Revised Manuscript received on 18 May 2022. | Manuscript published on 30 June 2022. | PP: 7-9 | Volume-11 Issue-7, June 2022. | Retrieval Number: 100.1/ijitee.G99410611722 | DOI: 10.35940/ijitee.G9941.0611722
Open Access | Ethics and Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: In real life, the problems may be of infinite dimensions. Design of ingenious information structure, for minimizing complexity and redundancy of the problem space are versatile. This is unique in the sense: given an arbitrary ’n’ node graph the problem becomes countable infinite and in some cases it is uncountable infinite. Problems which can be mapped as graphs are normally simple in nature but we remember the adage “Simple things are mighty things”. What we mean that normally for example it is a practice to bring undue mathematics to make things complex but although the graph algorithms are of exponential complexity for large dimension.
Keywords: Intractability, Algorithm, Complexity, problems, NP, NP-Complete, NP-Hard, Approximation Algorithm, Heuristic, Reducibility.
Scope of the Article: Analysis of Algorithms and Computational Complexity