A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence. (September 2014)

• Record Type: Journal Article
• Authors: JACQUET, PHILIPPE; KNESSL, CHARLES; SZPANKOWSKI, WOJCIECH; Broutin, Nicolas; Fill, James Allen; Nebel, Markus; Ward, Mark Daniel
• Is Part Of: Combinatorics, probability and computing. Volume 23:Number 5(2014:Sep.)
• Page Start: 829
• Page End: 841
• Publication Date: 2014-09
• Subjects: Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000133
• Languages: English
• ISSNs: 0963-5483

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>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.</p> </abstract>