The Art of Computer Programming, Volume 4, Fascicle 6: Satisfiability

In 1962 Donald Knuth sketched out chapter titles for a twelve chapter book on computer algorithms called The Art of Computer Programming Chapter 7 was to cover combinatorial algorithms algorithms having to do with the arrangement of objects into patterns As Knuth himself put it At that time I decided to include a brief chapter about combinatorial algorithms just for fun Hey look most people use computers to deal with numbers but we can also write programs that deal with patterns In those days it was easy to give a fairly complete description of just about every combinatorial algorithm that was known And even by 1966 when I d finished a first draft of about 3000 handwritten pages for that already overgrown book fewer than 100 of those pages belonged to Chapter 7 from the preface to volume 4A of TAOCP Well needless to say he underestimated the scope of the problems and the resources eventually devoted to working on them This is the second fascicle in volume 4B This multivolume work on the analysis of algorithms has long been recognized as the definitive description of classical computer science The four volumes published to date already comprise a unique and invaluable resource in programming...readmore