ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let \opcatSA\opcat{SA} be the category whose objects are embedded semi-algebraic sets and whose morphisms are restrictions of polynomial mappings. Let \cA\cA consist of scalar multiplication, addition, multiplication, the inclusion [0,∞)↪R[0,\infty)\hookrightarrow\mathbb{R}, and the morphism R→0\mathbb{R}\to 0. 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 \opcatSA\opcat{SA}. Single-exponential mixed complexity conjecture. The function

Cc\opcatSA\scalebox0.5∙→\scalebox0.5∙,\cA\opmixed(\opim\opcatSA)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}})

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.