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