Talk:Immerman–Szelepcsényi theorem

"In its general form the theorem states that NSPACE = co-NSPACE. In other words, if a nondeterministic machine can solve a problem, it can solve its complement problem (with the yes and no answers reversed) in the same asymptotic amount of space."

This is stated as if it were an equivalence, but is it? I mean, the fact that NSPACE = coNSPACE does not necessarily imply that the complement of a problem can be solved in the *same* asymptotic amount of space (the theorem says this, but this is stronger than NSPACE = coNSPACE). Isn't NSPACE = coNSPACE anyway a trivial consequence of Savitch's theorem, since PSPACE is closed uner complementation and PSPACE = NPSPACE? So the real content of Immerman-Szelepcsényi is that the complement of L in NSPACE(s(n)) is also in NSPACE(s(n)), instead of just NSPACE(s(n)^2), which is implied by Savitch's theorem. Or am I missing something?

"NSPACE = co-NSPACE" is a shorthand for "NSPACE(s) = co-NSPACE(s) for all reasonable functions s". It does not have anything particular to do with PSPACE, and it is not implied by Savitch's theorem, because the extra square makes the function asymptotically bigger. You may be confusing NSPACE with NPSPACE. — Emil J. 13:16, 22 May 2009 (UTC)[reply]

padding

Someone wrote " although this is the special case when s(n) = log n, it implies the general theorem by a standard padding argument." Could he gives references ? because as far as I can tell, for function f such that log(n)<<f(n)<<n there is no working padding argument. A padding argument would work for classes bigger than n, and only because it can use the NSPACE(n)=coNSPACE(n) theorem.

As far as I can tell, it's false, if I'm wrong and someone have the reference, just remove the "reference needed" reference. And Immerman's article make a direct proof and never spoke of padding argument (and it would be nice if he can leave a message on my talk page, since I would really want a reference for my current research).

I also added the fact that the log hierarchy collapse, which is proved in the same article and a non-trivial corollary Arthur MILCHIOR (talk) 06:58, 31 July 2010 (UTC)[reply]

If I remember correctly, a detailed proof is given in Papadimitriou's 1994 book on computational complexity. Unfortunately, I do not have it at hand to look it up. A reference accessible online is the draft of Chapter 4 of Arora and Barak's book. Admittedly, the "proof" of Corollary 4.19 is very sketchy (although it is not difficult). Be aware of the technical pitfall that the function f has to be "reasonable", that is, space constructible. If someone can easily access Papadimitriou's book, please include a reference to the chapter and Theorem number, so that curious readers can look it up. Hermel (talk) 11:04, 31 July 2010 (UTC)[reply]

Hermel, I read your link, he states the result but does not give the proof, and don't state it is a padding argument (I can't find anyline explaining the result). But Immerman's proof work directly for any function (not even space constructible as you can read in Immerman's article). Arthur MILCHIOR (talk) 06:21, 1 August 2010 (UTC)[reply]

I believe I added that line a few months ago. I don't see why the standard padding argument does not work. Let's try to show that NL = coNL implies NSPACE(log^2(n)) = coNPSPACE(log^2(n)).

Let L be in NSPACE(log^2(n)). We want to show that L is also in coNSPACE(log^2(n)). For each input x, create a padded version x', which is x followed by 2^{log^2(|x|)} zeroes. The size of this input is now |x| + 2^{log^2(|x|)}, which is basically 2^{log^2(|x|)} since that is bigger than |x|. This can be decided in NPSPACE(log^2(|x|)), where the input size |x'| is 2^{log^2(|x|)}. Thus the algorithm runs in the logarithm of the input size. Now using NL = coNL, we know there is a coNL algorithm that does the same thing. So we can take that machine and make it work on the original input by simulating the padded input and keeping track of when the head goes on to the zeroes, and taking care of that. This gives an coNSPACE algorithm that runs in ~~time~~ space log^2(n). This shows L is also in coNPSPACE(log^2(n)). By symmetry, NSPACE(log^2(n)) = coNPSPACE(log^2(n)). --Robin (talk) 15:02, 31 July 2010 (UTC)[reply]

I assume you mean "in space log^2(n)" and not "in time log^2(n)". We do not speak of time here. Else, thank you for your proof, it helps me a little bit. Arthur MILCHIOR (talk) 06:21, 1 August 2010 (UTC)[reply]

Yes, of course. Fixed! --Robin (talk) 14:39, 1 August 2010 (UTC)[reply]

Can you really afford to pad 2^{log^2(|x|)}, given that there's only O(log^2|x|) space available on the work tape? -- Andyx96 (talk) 03:48, 8 November 2018 (UTC)[reply]

Isn't that exactly how much space you need to count that high? —David Eppstein (talk) 04:24, 8 November 2018 (UTC)[reply]

Proof

Whether or not the padding argument works, the "proof" that the complement of a particular NL-complete language is in NL does not mean the complement of any NL language is in NL. And the proof isn't referenced, anyway. It's not in Immerman, and there is a perfectly good proof there. — Arthur Rubin (talk) 15:20, 16 August 2014 (UTC)[reply]

If a language is complete for coNL under logarithmic space many-one reductions (like the directed non-reachability problem) and that language is in NL, then coNL = NL, similar to how coNP = NP if a coNP-complete problem is in NP. J. Finkelstein (talk) 17:57, 7 December 2015 (UTC)[reply]