DocumentCode :
3158561
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
fYear :
2010
fDate :
28-30 June 2010
Firstpage :
132
Lastpage :
137
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Cybernetics and Intelligent Systems (CIS), 2010 IEEE Conference on
Conference_Location :
Singapore
Print_ISBN :
978-1-4244-6499-9
Type :
conf
DOI :
10.1109/ICCIS.2010.5518569
Filename :
5518569
Link To Document :
بازگشت