The nontrivial-invariant analogue of Valiant's conjecture

About 13 years old · traced to

Let k=R\mathbf{k}=\mathbb{R} or C\mathbb{C}, and let K0=K0(sa⁡R)K_0=K_0(\operatorname{sa}_\mathbb{R}) when k=R\mathbf{k}=\mathbb{R} and K0=K0(Var⁡C)K_0=K_0(\operatorname{Var}_\mathbb{C}) when k=C\mathbf{k}=\mathbb{C}. Let inv:K0→A\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.

VPkA≠VNPkinv.\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.

References

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.