Recurrence-Based Reductions for Inclusion and Exclusion Algorithms Applied to P Problems
- Creators
- 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
Name | Size | Download all |
---|---|---|
md5:0cdd53424a3a0f34df9b9d16c19f61dc
|
2.3 MB | Download |
md5:d60f4a23d7bc3b82f7aad0cce2080482
|
1.1 MB | Preview Download |
Additional details
- Eprint ID
- 26923
- Resolver ID
- CaltechCSTR:1996.cs-tr-96-01
- NSF Predoctoral Fellowship
- Created
-
2002-03-07Created from EPrint's datestamp field
- Updated
-
2019-10-03Created from EPrint's last_modified field
- Caltech groups
- Computer Science Technical Reports