Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 7, 2002 | Submitted
Report Open

Recurrence-Based Reductions for Inclusion and Exclusion Algorithms Applied to P Problems

Bax, Eric

Abstract

There are inclusion and exclusion algorithms for many #P problems. By imposing a hierarchy on the inclusion and exclusion formula's terms, we develop general reductions for inclusion and exclusion algorithms. We outline sufficient steps to tailor the general reductions to specific problems, and we ilustrate this process by applying it to algorithms for several #P problems. We test the reductions on the problem of counting Hamiltonian paths. Within the framework of the general reductions, we develop the concepts or zero sets and vestigial elements, and we present problem decomposition strategies. Also, we show how the reductions can be applied to algorithms that give approximate solutions to #P problems.

Additional Information

© 1996 California Institute of Technology. January 23, 1996. I thank three great teachers at Furman University: Dr. Douglas Rall for introducing me to combinatorics and to research, Dr. P. M. Cook for listening and guidance, and Or. Hayden Porter for teaching me two concepts that are central to this work - recursion and abstraction. Thanks to Dr. Andras Recski at MTKI in Budapest for teaching me when I was a student there, and also for taking the time to read my papers and point me in useful directions when I walked into his office out of the blue several years later. I thank Dr. Joel Franklin for showing an interest in this work, for listening patiently as I tried to explain it, and for supplying just the right information at just the right time. I thank my advisor Dr. Yaser S. Abu-Mostafa for his support, advice, and example. Supported by an NSF fellowship.

Attached Files

Submitted - TR-96-01.pdf

Submitted - TR-96-01.ps

Files

TR-96-01.pdf
Files (3.4 MB)
Name Size Download all
md5:0cdd53424a3a0f34df9b9d16c19f61dc
2.3 MB Download
md5:d60f4a23d7bc3b82f7aad0cce2080482
1.1 MB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 24, 2023