American Mathematical Society TranslationsSeries 2 1997; 189 pp; hardcover Volume: 178 ISBN10: 0821803867 ISBN13: 9780821803868 List Price: US$101 Member Price: US$80.80 Order Code: TRANS2/178
 This collection contains translations of papers on propositional satisfiability and related logical problems which appeared in Problemy Sokrashcheniya Perebora, published in Russian in 1987 by the Scientific Council "Cybernetics" of the USSR Academy of Sciences. The problems form the nucleus of this intensively developing area. This translation is dedicated to the memory of two remarkable Russian mathematicians, Sergei Maslov and his wife, Nina Maslova. Maslov is known as the originator of the inverse method in automated deduction, which was discovered at the same time as the resolution method of J. A. Robinson and has approximately the same range of applications. In 1981, Maslov proposed an iterative algorithm for propositional satisfiability based on some general ideas of search described in detail in his posthumously published book, Theory of Deductive Systems and Its Applications (1986; English 1987). This collection contains translations of papers on proposititional satisfiability and related logical problems. The papers related to Maslov's iterative method of search reduction play a significant role. Readership Graduate students and research mathematicians working in mathematical logic, theory of algorithms, and in related areas of computer science. Table of Contents  R. I. Freidzon  Algorithmics of \(NP\)hard problems
 E. Ya. Dantsin  Algorithmics of propositional satisfiability problems
 V. Ya. Kreinovich  Semantics of S. Yu. Maslov's iterative method
 M. I. Zakharevich  Ergodic properties of Maslov's iterative method
 I. V. Melichev  Anomalous properties of Maslov's iterative method
 Yu. V. Matiyasevich  Possible nontraditional methods of establishing unsatisfiability of propositional formulas
 G. V. Davydov and I. M. Davydova  Dual algorithms in discrete optimization
 A. Ya. Dikovsky  Models, methods, and modes for the synthesis of program schemes
 M. I. Kanovich  Effective calculi as a technique for search reduction
 N. K. Kossovskiĭ  Lower bounds of combinatorial complexity for exponential search reduction
 An. A. Muchnik  On a class of polynomial systems of equations following from the formula for total probability and possibilities for eliminating search in solving them
 V. Kreinovich  S. Maslov's iterative method: 15 years later (freedom of choice, neural networks, numerical optimization, uncertainty reasoning, and chemical computing)
