$P_\mathbb R$ is the set of languages decidable in polynomial time over the real $BSS$ machine defined in https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine.

Let $0-1-P_\mathbb R=\{L\in\{0,1\}^*:L\in P_\mathbb R\}$.

Is it known $NP\subseteq 0-1-P_\mathbb R$ holds?

What is the consequence if $NP\subseteq 0-1-P_\mathbb R$ holds?

  • $\begingroup$ Could you define what a $BSS$ machine is for those unfamiliar? $\endgroup$
    – Jake
    May 25, 2022 at 18:30
  • 1
    $\begingroup$ In sciencedirect.com/science/article/pii/030439759300063B it is proved that the additive $BSS$ machines (no multiplication or division) capture $P/poly$ over Boolean inputs. I don't know what happens if we allow multiplication and/or division. $\endgroup$ May 30, 2022 at 18:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.