Note that both graph isomorphism and integer factorization are problems that may well lie in P, so these aren’t great examples. Traveling salesman is a bit better.
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.
Note that both graph isomorphism and integer factorization are problems that may well lie in P, so these aren’t great examples. Traveling salesman is a bit better.
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.