Can somebody please explain to me why NPSPACE=PSPACE in a simple way?

Asked Apr 15 '21 at 11:41

Active Apr 15 '21 at 11:53

Viewed 458 times

This is what I found on the web, but why is this true? Can somebody explain it as simply as possible, please?

In other words, if a nondeterministic Turing machine can solve a problem using f(n) space, an ordinary deterministic Turing machine can solve the same problem in the square of that space bound.

edited Apr 15 '21 at 11:53

MJD

65,394
39
298
580

asked Apr 15 '21 at 11:41

Benny

Have you found Savitch's Theorem on the web? – Gerry Myerson Apr 15 '21 at 13:06
@Get In other words, if a nondeterministic Turing machine can solve a problem using f(n) space, an ordinary deterministic Turing machine can solve the same problem in the square of that space bound. But how is this proved? – Benny Apr 15 '21 at 13:08
1

So, you don't like the proof at https://en.wikipedia.org/wiki/Savitch%27s_theorem#Proof ? or any of the links given at that page? http://www.cs.ecu.edu/karl/6420/spr16/Notes/PSPACE/savitch.html or https://youtu.be/VW1efHamKAs or https://youtu.be/mTsBA1c7yIw or https://courses.cs.washington.edu/courses/cse431/14sp/scribes/lec16.pdf – Gerry Myerson Apr 15 '21 at 23:36
1

Or https://cs.stackexchange.com/questions/22745/the-crux-of-savitchs-theorem – Gerry Myerson Apr 15 '21 at 23:42
1

Have you had a look at those links, Benny? – Gerry Myerson Apr 17 '21 at 03:17
Are you still here, Benny? – Gerry Myerson Apr 18 '21 at 23:27
@GerryMyerson Yeah ty it helped me – Benny Apr 19 '21 at 15:48

Can somebody please explain to me why NPSPACE=PSPACE in a simple way?

0 Answers0