In this paper: ‘Classical Spin Models and the Quantum-Stabilizer Formalism’, M. Van den Nest, W. Dür, and H. J. Briegel, Phys. Rev. Lett. 98, 117207 (2007).

The authors mention at some point that: “For example, nonplanar graphs of large tree-width would typically

give rise to states where MQC (Measurement based quantum computing) is NP-hard to simulate classically.” If simulating MQC classically is NP-hard, doesn’t this mean that a physical implementation of MQC can solve NP-complete problems? ]]>

Thanks to Matthew P. Johnson and you for answering my question.

]]>you say CGI animation is a solved problem. And yet… it is interesting to see that vast majority of cgi animation films, at least good ones, like Pixar fare, are about cartoonish characters that are not human. Even humans, when present, are decidedly cartoonish. This is smart – CGI animation has not reached yet the film-realistic level (and arguably it does need to be to make good films). By film-realistic I mean looking like real humans acting. One might imagine a test for CGI animation that parallels Turing test for machine intelligence: can you make a 2-hour film where humans are entirely simulated by CGI, which would fool humans into thinking that these are human actors? You can imagine there being a lesser test – film mainly focusing on body motion, and a greater test – film focusing on facial expressions, conveying emotion. We are optimized by millenia of evolution to be good at both tasks – appreciation of animal bodies moving, and perception of minutiae of facial expressions. So, assuming the film audience are not doofuses (oh, and assuming you are simulating somebody with a bit more depth than Schwarzenegger) – how long until CGI would pass such test? Care to speculate?

]]>-
Supposedly, the subset is extremely close to trivial, i.e., almost all of them (!):

“The halting problem for Turing machines is decidable on a set of asymptotic probability one. Specifically, there is a set B of Turing machine programs such that (i) B has asymptotic probability one, so that as the number of states n increases, the proportion of all n-state programs that are in B goes to one; (ii) B is polynomial time decidable; and (iii) the halting problem H intersect B is polynomial time decidable. The proof is sensitive to the particular computational model.”

“The halting problem is decidable on a set of asymptotic probability one”

http://arxiv.org/abs/math/0504351

Yes, there’s hope to get into a decent school even without a research record. However, you’ll greatly increase your chances if you apply broadly — i.e. to 20 or 30 places and not just to Berkeley, Stanford, MIT, etc. Not knowing more about you I can’t recommend specific places.

]]>