## [My Computational Complexity Web Log] Foundations of Complexity Lesson 19: The Immerman-Szelepcsényi Theorem

Expand Messages
• Previous Lesson In this lesson we will prove the Immerman-Szelepcsnyi Theorem. Theorem (Immerman-Szelepcsnyi): For reasonable s(n) log n,
Message 1 of 1 , Jun 3, 2003
Previous Lesson

In this lesson we will prove the Immerman-Szelepcsényi Theorem.

Theorem (Immerman-Szelepcsényi): For reasonable s(n)≥ log n, NSPACE(s(n))=co-NSPACE(s(n)).

Let M be a nondeterministic machine using s(n) space. We will create a nondeterministic machine N such that for all inputs x, N(x) accepts if and only if M(x) rejects.

Fix an input x and let s=s(|x|). The total number of configurations of M(x) can be at most cs for some constant c. Let t=cs. We can also bound the running time of M(x) by t because any computation path of length more than t must repeat a configuration and thus could be shortened.

Let I be the initial configuration of M(x). Let m be the number of possible configurations reachable from I on some nondeterministic path. Suppose we knew the value of m. We now show how N(x) can correctly determine that M(x) does not accept.

Let r=0
For all nonaccepting configurations C of M(x)
Try to guess a computation path from I to C
If found let r=r+1
If r=m then accept o.w. reject

If M(x) accepts then there is some accepting configuration reachable from I so there must be less than m non-accepting configurations reachable from I so N(x) cannot accept. If M(x) rejects then there is no accepting configurations reachable from I so N(x) on some nondeterministic path will find all m nonaccepting paths and accept. The total space is at most O(s) since we are looking only at one configuration at a time.

Of course we cannot assume that we know m. To get m we use an idea called inductive counting. Let mi be the number of configurations reachable from I in at most i steps. We have m0=1 and mt=m. We show how to compute mi+1 from mi. Then starting at m0 we compute m1 then m2 all the way up to mt=m and then run the algorithm above.

Here is the algorithm to nondeterministically compute mi+1 from mi.

Let mi+1=0
For all configurations C
Let b=0, r=0
For all configurations D
Guess a path from I to D in at most i steps
If found
Let r=r+1
If D=C or D goes to C in 1 step
Let b=1
If r<mi halt and reject
Let mi+1=mi+1+b

The test that r<mi guarantees that we have looked at all of the configurations D reachable from I in i steps. If we pass the test each time then we will have correctly computed b to be equal to 1 if C is reachable from I in at most i+1 steps and b equals 0 otherwise.

We are only remembering a constant number of configurations and variables so again the space is bounded by O(s). Since we only need to remember mi to get mi+1 we can run the whole algorithm in space O(s).

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 6/3/2003 2:09:50 PM
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://groups.yahoo.com/neo/groups/complexityweblog/conversations/topics/59?xm=1&m=p&l=1", "fetch_time": 1508594845000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2017-43/segments/1508187824819.92/warc/CC-MAIN-20171021133807-20171021153807-00447.warc.gz", "warc_record_offset": 713811513, "warc_record_length": 19809, "token_count": 769, "char_count": 2921, "score": 3.703125, "int_score": 4, "crawl": "CC-MAIN-2017-43", "snapshot_type": "latest", "language": "en", "language_score": 0.826013445854187, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00002-of-00064.parquet"}