Forums before death by AOL, social media and spammers... "We can't have nice things"
|    comp.compilers    |    Compiler construction, theory, etc. (Mod    |    2,753 messages    |
[   << oldest   |   < older   |   list   |   newer >   |   newest >>   ]
|    Message 2,383 of 2,753    |
|    SLK Mail to All    |
|    =?utf-8?B?T1Q6IFByb29mIHRoYXQgUOKJoE5Q?=    |
|    09 Aug 16 12:24:46    |
      From: slkpg4@gmail.com              A constructive proof is given to show that the complement of non-SLL(k)       testing is not in NP. The proof focuses on the verification step of       determining membership in NP. An instance of the problem is shown to       generate an intractable number of items that must be verified, making the       nondeterministic solution unverifiable in polynomial time. Since       non-SLL(k) testing is well known to be NP-complete, the complement of an       NP-complete problem is not in NP, so it follows that NPb coNP. Here the       abreviation SLL(k) means strong LL(k), not its original usage for simple       LL(k).              http://www.slkpg.com/NPcoNP.html              --- SoupGate-Win32 v1.05        * Origin: you cannot sedate... all the things you hate (1:229/2)    |
[   << oldest   |   < older   |   list   |   newer >   |   newest >>   ]
(c) 1994, bbs@darkrealms.ca