OT: Proof that P≠NP

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	OT: Proof that P≠NP
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> (permalink)
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

Show key headers only | View raw

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

Back to comp.compilers | Previous | Next | Find similar | Unroll thread

Thread

OT: Proof that P≠NP "SLK Mail" <slkpg4@gmail.com> - 2016-08-09 12:24 -0800

csiph-web