Jump to content

Talk:Walter Savitch

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Untitled

[edit]

I deleted the following:

NL was the first formally defined complete language and has subsequently lead to a large body of research in computational complexity theory.

It doesn't make sense (NL is a class, not a language). I also don't think its true; many-one reductions were not fully formalized until Cook. I could be wrong, but it needs a citation in any case.