Does the MIP* = RE result algebrize? (It doesn’t relativize, as noted here.)
If it doesn’t algebrize, is there a more complicated similar notion that it does satisfy?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Algebraization is about complexity while re is about computability. $\endgroup$ – VS. Mar 7 '20 at 22:43
-
$\begingroup$ I would it is no. $\endgroup$ – VS. Mar 7 '20 at 22:52
-
$\begingroup$ @VS. this comment would also have applied to relativization, wouldn't it? (sorry, updated my comment while you were answering, now the order is messed up) $\endgroup$ – Clement C. Mar 7 '20 at 22:52
-
$\begingroup$ @VS. Please feel free to write up an answer if your intuition can be expanded into a proof or argument. As it is I'm not sure how to interpret "complexity" vs. "computability" formally: both notions are about sets of languages, and the question is already a well-defined question about sets of languages. $\endgroup$ – Geoffrey Irving Mar 10 '20 at 11:09
Add a comment
|
