Polynomial-time conjecture for quadrilateral-to-standard solution set conversion
Polynomial-time conjecture for quadrilateral-to-standard solution set conversion
Let be the number of tetrahedra and let denote the size of the standard solution set produced by Algorithm~ for converting a quadrilateral solution set to a standard solution set. Polynomial-time conjecture. The time complexity of Algorithm~ is at worst polynomial in the size of the output; equivalently, its running time is at most a polynomial function of and . This proposal is motivated by empirical evidence that the algorithm's intermediate lists do not undergo the combinatorial explosion seen in general double description methods, and that conversion is negligible compared with enumeration. The statement remains unproved in the supplied text.
Sources & referencesView supporting material
Primary source
Benjamin A. Burton, “Converting between quadrilateral and standard solution sets in normal surface theory”, arXiv:0901.2629 (2009).
Additional references
2 papers in this index state this conjecture (2000–2009). The statement above is taken from the most recent of them; the others are arXiv:math/0003125.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.