Expected-case analysis with semirandom data models.
Douglas M. Van Wieren · Deep Blue (University of Michigan) · 1999
With the intent of settling practical questions in recognizing the average-case complexity of a fixed NP-hard problem with a given random distribution on input, this thesis provides a well-founded semi-random model. The development is mathematical, starting from a basis involving semi-random bit strings. The object is a set of practical theoretical tools meant to increase the modularity of analytical results. The result provides a continuous abstraction between worst-case and average-case analyses, described in the thesis as expected-case analysis. Analytic demonstrations with a semi-random model are immediately applicable to random submodels. Most published algorithms analyzed for the average case apply only in very narrow circumstances, and few positive results convey more than a suggestion of applicability to practical situations. This forms an impediment to the serious pursuit of formal methods with regard to expectations. In contrast, the methods provided in the thesis not only provide for the natural re-use of previously obtained analytic material, but also simplify the production of such material. As a demonstration, problems related to Hamiltonian cycles on semi-random graph models are investigated, and the range of known, efficient-on-average solutions for problem are extended significantly. The algorithms shown are for both randomized and non-randomized architectures, and emphasize parallel portability. Many of these positive results are not accessible with other techniques, and the insights obtained are theoretically interesting in their own right. In additional to practical concerns with making analytic efforts more productive, the thesis modestly addresses some of the limitations on what can be shown, and provides a new perspective on problem complexities and architecture assumptions. Some data models are shown to present NP-related difficulties; others, RNP-related difficulties. For the Hamiltonian cycle problem, it is shown that both situations arise in semi-random models which narrow in upon threshold random graphs.