10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Algebraization is about complexity while re is about computability. $\endgroup$ – VS. Mar 7 at 22:43
  • $\begingroup$ I would it is no. $\endgroup$ – VS. Mar 7 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 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 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.