Complexity yardsticks for \(f\)-vectors of polytopes and spheres (Q2197688)

The face numbers of simple polytopes are characterized by the \(g\)-theorem, conjectured by \textit{P. McMullen} [Isr. J. Math. 9, 559--570 (1971; Zbl 0209.53701)] and proved by \textit{R. P. Stanley} [Ann. N. Y. Acad. Sci. 440, 212--223 (1985; Zbl 0573.52008)] and by \textit{L. J. Billera} and \textit{C. W. Lee} [J. Comb. Theory, Ser. A 31, 237--255 (1981; Zbl 0479.52006)]. The related \(f\)-vectors and flag \(f\)-vectors of general \(d\)-polytopes and regular \(CW\) \((d-1)\)-spheres are not well understood, despite considerable efforts. In this note the author proposes approaching the qualitative differences between \(f\)-vectors and flag \(f\)-vectors of these classes by comparing their computational complexity, in terms of geometric and computational measures.