<p><span class="math-container">$P_\mathbb R$</span> is the set of languages decidable in polynomial time over the real <span class="math-container">$BSS$</span> machine defined in <a href="https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine</a>.</p>
<p>Let <span class="math-container">$0-1-P_\mathbb R=\{L\in\{0,1\}^*:L\in P_\mathbb R\}$</span>.</p>
<blockquote>
<p>Is it known <span class="math-container">$NP\subseteq 0-1-P_\mathbb R$</span> holds?</p>
</blockquote>
<blockquote>
<p>What is the consequence if <span class="math-container">$NP\subseteq 0-1-P_\mathbb R$</span> holds?</p>
</blockquote>

CC BY-SA 4.0
2022-05-25T18:30:54.853Z
Could you define what a $BSS$ machine is for those unfamiliar?
Jake
CC BY-SA 4.0
2022-05-30T18:24:26.710Z
In https://www.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.
Reijo Jaakkola
<np-hardness><turing-machines><np><p-vs-np><computing-over-reals>
Relation between BSS and Turing models
Turbo
# Relation between BSS and Turing models

(Asked by: username_0 on 2022-05-24)

$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?

**Tags:** np-hardness, turing-machines, np, p-vs-np, computing-over-reals

> **Comments:**
> **username_1**: Could you define what a $BSS$ machine is for those unfamiliar?  
> **username_2**: In https://www.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.  

---

## 0 answers

