如果 A 在 RP 中，并且存在从 B 到 A 的多项式时间减少，那么 B 在 RP 中？
If A is in RP and there is a polynomial time reduction from B to A then B in RP?
我认为这是真的，因为你可以将 B 简化为 A，然后 运行 A 的概率算法，如果我们得到拒绝，那么 B 也是拒绝的，如果输入在 A 中，我们会得到一个接受，这意味着如果输入在 B 中，至少有一半的时间我们会得到一个接受。所以 B 在 RP 中，但我不确定。
如果反过来减少会怎样？如果A在RP中并且从A到B存在多项式时间减少，那么B在RP中吗？
从 B 减少到 A：
有个问题。如果 B 的所有实例恰好映射到拒绝的 A 实例怎么办？ :)
这可能会发生，因为 B 可能仍有超过 50% 的真实实例接受，但这些实例不在您的缩减图像中。
从 A 减少到 B：
关于你的第二个问题，考虑一下：我们可以将 A 简化为 halting problem，如下所示：
- 运行我们的RP算法a.
- 如果答案是肯定的，return是的。否则，进入死循环。
这是否意味着停机问题在 RP 中？ :)
我认为这是真的，因为你可以将 B 简化为 A，然后 运行 A 的概率算法，如果我们得到拒绝，那么 B 也是拒绝的，如果输入在 A 中，我们会得到一个接受，这意味着如果输入在 B 中，至少有一半的时间我们会得到一个接受。所以 B 在 RP 中，但我不确定。
如果反过来减少会怎样？如果A在RP中并且从A到B存在多项式时间减少，那么B在RP中吗？
从 B 减少到 A：
有个问题。如果 B 的所有实例恰好映射到拒绝的 A 实例怎么办？ :)
这可能会发生，因为 B 可能仍有超过 50% 的真实实例接受，但这些实例不在您的缩减图像中。
从 A 减少到 B：
关于你的第二个问题，考虑一下：我们可以将 A 简化为 halting problem，如下所示：
- 运行我们的RP算法a.
- 如果答案是肯定的，return是的。否则，进入死循环。
这是否意味着停机问题在 RP 中？ :)