Single-exponential mixed complexity conjecture for the semi-algebraic image functor
Single-exponential mixed complexity conjecture for the semi-algebraic image functor
Let be the category whose objects are embedded semi-algebraic sets and whose morphisms are restrictions of polynomial mappings. Let consist of scalar multiplication, addition, multiplication, the inclusion , and the morphism . Write C_{c^{\op{mixed}}_{\opcat{SA}^{\raisebox{0.009cm}{\scalebox{0.5}{\bullet}} \to \raisebox{0.009cm}{\scalebox{0.5}{\bullet}}},\cA}}(\op{im}_{\opcat{SA}}) for the mixed computational complexity of the image functor on . Single-exponential mixed complexity conjecture. The function
is bounded singly exponentially. This is presented as a categorical analogue of the P versus NP question for semi-algebraic sets; the surrounding text says that mixed computation is more powerful than limit computation and that the authors are unable to resolve the corresponding polynomial-boundedness question, so the conjectured single-exponential bound remains open.
Sources & referencesView supporting material
Primary source
Saugata Basu and M. Umut Isik, “Categorical Complexity”, arXiv:1610.07737 (2019).
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.