home bbs files messages ]

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