News for hackers. Stuff that matters.
Re:Landmark computer science proof cascades through physics ... by lwneal on Thursday March 05, 2020 @02:57AM (#22491748)
The paper[1] claims that MIP* = RE. At first I wasn't sure whether that was true, because the paper is too long and complicated for me to verify.

But then I found a series of questions and answers written by this quantum guy Scott Aaronson[2] and by this other quantum guy Kenneth Regan[3], who both know a bunch of quantum stuff. Each one of their blog posts makes me more certain about MIP* = RE, to the point that now I'm 99.9% sure it's true, even though I could never verify it myself.

[1] https://arxiv.org/abs/2001.04383

[2] https://www.scottaaronson.com/blog/?p=4512

[3] https://rjlipton.wordpress.com/2020/01/15/halting-is-poly-ti...

Re:Landmark computer science proof cascades through physics ... by peterburkimsher on Thursday March 05, 2020 @03:36AM (#22491919)
I hadn't heard of Aaronson or Regan before, but perhaps they communicate, and therefore their blog posts might be correlated.

From the new proof though, I'm certain that I can't put an upper or lower bound on the probability of whether they're right.

Re:Landmark computer science proof cascades through physics ... by titanomachy on Thursday March 05, 2020 @04:23AM (#22492138)
They do communicate, but only nonclassically.
Re:Landmark computer science proof cascades through physics ... by bjornsing on Thursday March 05, 2020 @06:20AM (#22492621)
No, they don’t communicate. They use entangled particles to coordinate their blog posts. :P
Re:Landmark computer science proof cascades through physics ... by fortydegrees on Thursday March 05, 2020 @04:42AM (#22492233)
Start with 100 and 0 and go from there
Re:Landmark computer science proof cascades through physics ... by peterburkimsher on Thursday March 05, 2020 @05:17AM (#22492374)
What about complex numbers in probabilities?
Re:Landmark computer science proof cascades through physics ... by bergoid on Thursday March 05, 2020 @06:59AM (#22492825)
Their modulus squared gives you the probability.

https://en.wikipedia.org/wiki/Probability_amplitude

Re:Landmark computer science proof cascades through physics ... by xenonite on Thursday March 05, 2020 @06:37AM (#22492706)
They „denote by MIP the class of languages that have multiprover interactive proof systems,“ and by „MIP∗, the ‚entangled-prover‘ analogue of the class MIP. Informally the class MIP∗, first introduced in [CHTW04], contains all languages that can be decided by a classical polynomial-time verifier interacting with multiple quantum provers sharing entanglement.“
Re:Landmark computer science proof cascades through physics ... by iamvik on Thursday March 05, 2020 @03:50AM (#22491995)
very meta
Re:Landmark computer science proof cascades through physics ... by raverbashing on Thursday March 05, 2020 @06:47AM (#22492763)
So, from reading a bit, it seems MIP* was proven harder than it was thought to be, correct?
Re:Landmark computer science proof cascades through physics ... by jconnop on Thursday March 05, 2020 @03:36AM (#22491920)
Perhaps Scott and Kenneth were in cahoots.