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

0 |

8/9/2016 8:24:46 PM