Neil Immerman

算量の考え方によって、計算複雑性理論と数理論理学の成果の交流が可能となり、標準的な複雑性クラスが「自然」なものであるという証拠も与える。Neil Immerman は、「数理論理学の歴史の中でも、有限構造に関する研究が最も興味深く…さらに言えば、コンピュータ上のオブジェクトは常に有限である。計算の

500以上の複雑性クラスとその特性のリスト A diagram of the world of computability and complexity by Neil Immerman - 複雑性クラスの階層についての図 Michael Garey, and David S. Johnson: Computers and

116, 1993, pp. 3-31. Neil Immerman. Languages Which Capture Complexity Classes. 15th ACM STOC Symposium, pp.347-354. 1983. Neil Immerman's descriptive

NL かどうかは未だわかっていない。非決定性領域は補集合演算について閉じているため、NL = co-NL であることが判っている。これは、Neil Immerman と Róbert Szelepcsényi が 1987年にそれぞれ独自に証明した。彼らはこの業績によって1995年のゲーデル賞を受賞

sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf  ^ Immerman, Neil (1988), “Nondeterministic space is closed under complementation”, SIAM