Tue, 09 Aug 2016 12:24:46 -0800

Related articles |
---|

=?utf-8?B?T1Q6IFByb29mIHRoYXQgUOKJoE5Q?= slkpg4@gmail.com (SLK Mail) (2016-08-09) |

From: | "SLK Mail" <slkpg4@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Tue, 09 Aug 2016 12:24:46 -0800 |

Organization: | SLK Systems |

Injection-Info: | miucha.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="82445"; mail-complaints-to="abuse@iecc.com" |

Keywords: | theory |

Posted-Date: | 11 Aug 2016 17:05:54 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.