The nontrivial-invariant analogue of Valiant's conjecture

Let k=R\mathbf{k}=\mathbb{R} or C\mathbb{C}, and let K0=K0(saR)K_0=K_0(\operatorname{sa}_\mathbb{R}) when k=R\mathbf{k}=\mathbb{R} and K0=K0(VarC)K_0=K_0(\operatorname{Var}_\mathbb{C}) when k=C\mathbf{k}=\mathbb{C}. Let inv:K0A\mathrm{inv}:K_0\rightarrow\mathbf{A} be a non-trivial additive invariant, where A\mathbf{A} is a polynomially bounded graded k\mathbf{k}-algebra. Analog of Valiant's conjecture.

VPkAVNPkinv.\mathbf{VP}_{\mathbf{k}}^{\mathbf{A}}\neq\mathbf{VNP}_{\mathbf{k}}^{\mathrm{inv}}.

This is the constructible-function analogue of Valiant's VP\mathbf{VP} versus VNP\mathbf{VNP} conjecture; the source presents it as an open separation question for every non-trivial additive invariant.

Sources & referencesView supporting material

Primary source

Saugata Basu, “A complexity theory of constructible functions and sheaves”, arXiv:1309.5905 (2017).

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.