Polynomial-time conjecture for quadrilateral-to-standard solution set conversion

Let nn be the number of tetrahedra and let kk' 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 nn and kk'. 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

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.