Linear average-case performance conjecture for MemberPN
Let be a binary word, and let be the proposed membership tester that applies the two linear-time rejection tests followed by a quadratic-time prefix-normality test. MemberPN average-case conjecture. The membership tester for prefix normal words functions in average-case time. The conjecture is motivated by decreasing empirical ratios in the reported experiments, but remains unproved in the source.
References
- Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták, Frank Ruskey and Joe Sawada, “Normal, Abby Normal, Prefix Normal”, arXiv:1404.2824 (2014).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.