Title :
Intelligent systems and polynomial solvability of NP-complete problems
Author :
Chaudhari, Narendra S.
Author_Institution :
Dept. of Comput. Sci. & Eng., Indian Inst. of Technol. (IIT), Indore, India
Abstract :
Many fundamental problems in automated theorem proving are known to be NP-Complete. In, we have given a polynomial algorithm for 3-SAT, one of the first NP-Complete problems. The result is unexpected and has deep consequences for the design of intelligent systems; hence, in this paper, we review our algorithmic approach for 3-SAT, and we give simplified analysis of our approach to demonstrate the polynomial bound of O(n13) operations. We also indicate the immediate and important consequences of our polynomial algorithm for 3-SAT for the design of intelligent systems.
Keywords :
computability; computational complexity; optimisation; polynomials; theorem proving; 3-SAT; NP-complete problems; automated theorem proving; intelligent systems; polynomial solvability; Algorithm design and analysis; Computer science; Intelligent systems; Logic; Microprocessors; NP-complete problem; Polynomials; algorithms - analysis of algorithms; theorem proving; theory of computation - complexity measures;
Conference_Titel :
Cybernetics and Intelligent Systems (CIS), 2010 IEEE Conference on
Conference_Location :
Singapore
Print_ISBN :
978-1-4244-6499-9
DOI :
10.1109/ICCIS.2010.5518569