🚀 go-pugleaf

                                PH.D. STUDENT TALKS

                University at Albany - State University of New York

                            Computer Science Department

                                       Ye Wu

                  Tuesday, December 2, 1997, at 4:00p.m. in LI-98

                            SAT Problem and Local Search

                                      Abstract

                 The satisfiability(SAT) problem is fundamental in solv-
            ing  many practical problems in  mathematical logic, machine
            learning, constraint  satisfaction,  and  very  large  scale
            integration(VSLI)  engineering. Theoretically, the SAT prob-
            lem is a core of a large family of computationally  intract-
            able  NP-complete  problems(SAT problem is the first problem
            proved to be NP-Completeness by Cook). Therefore, methods to
            solve the SAT problem play an important role in the develop-
            ment of computing theory and system.  There  are  many  dif-
            ferent  methods  trying  to solve SAT problem, I just try to
            show one of them-Local Search. I will give a brief  descrip-
            tion  of  some  local search algorithms and some interesting
            results.