• 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