Sure, though my impression is that people don’t think graph isomorphism actually is in P. And integer factorization turned out to be a problem for Harry. But you’re right, we can actually just simulate a nondeterministic Turing machine this way: every time you have a choice for which state to visit next, just listen as future you tells you which ones not to visit.
Sure, though my impression is that people don’t think graph isomorphism actually is in P. And integer factorization turned out to be a problem for Harry. But you’re right, we can actually just simulate a nondeterministic Turing machine this way: every time you have a choice for which state to visit next, just listen as future you tells you which ones not to visit.