Single-exponential mixed complexity conjecture for the semi-algebraic image functor
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.