Article contents
A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence
Published online by Cambridge University Press: 09 July 2014
Abstract
We resolve a conjecture proposed by D.E. Knuth concerning a recurrence arising in the satisfiability problem. Knuth's recurrence resembles recurrences arising in the analysis of tries, in particular PATRICIA tries, and asymmetric leader election. We solve Knuth's recurrence exactly and asymptotically, using analytic techniques such as the Mellin transform and analytic depoissonization.
Keywords
- Type
- Paper
- Information
- Combinatorics, Probability and Computing , Volume 23 , Issue 5: Honouring the Memory of Philippe Flajolet - Part 1 , September 2014 , pp. 829 - 841
- Copyright
- Copyright © Cambridge University Press 2014
References
- 1
- Cited by