Path: csiph.com!xmission!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!border2.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: "SLK Mail" <slkpg4@gmail.com>
Newsgroups: comp.compilers
Subject: =?utf-8?B?T1Q6IFByb29mIHRoYXQgUOKJoE5Q?=
Date: Tue, 09 Aug 2016 12:24:46 -0800
Organization: SLK Systems
Lines: 12
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <16-08-003@comp.compilers>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes
Content-Transfer-Encoding: 8bit
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
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:1725

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