Path: csiph.com!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.theory Subject: Re: Is NPC useless? Date: Wed, 12 Jun 2024 00:21:22 +0100 Organization: A noiseless patient Spider Lines: 32 Message-ID: <87msnr12x9.fsf@bsb.me.uk> References: <296ed519c7d2c9bfac06dc145f40fbabf765a3be.camel@gmail.com> <877cev3gpz.fsf@bsb.me.uk> <8ede5c7eb5a672de9bdaea8e7e4d038a8abc5194.camel@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Injection-Date: Wed, 12 Jun 2024 01:21:25 +0200 (CEST) Injection-Info: dont-email.me; posting-host="0aad59004189f766bcfedb04f35e75b3"; logging-data="1359883"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/b+rK8Y62ahWknInp6wvnENYfmVY3zlIg=" User-Agent: Gnus/5.13 (Gnus v5.13) Cancel-Lock: sha1:EV1ViAoThVpOr/SOk/njdpzbK3U= sha1:eoOfT5lrM1yiLQVNPZRl2reePWU= X-BSB-Auth: 1.490be4d867325bbfe2cf.20240612002122BST.87msnr12x9.fsf@bsb.me.uk Xref: csiph.com comp.theory:106946 wij writes: > On Tue, 2024-06-11 at 11:40 +0100, Ben Bacarisse wrote: >> wij writes: >> >> > NPC specifies a set of very significant problems, and identifies such >> > problems.  So, is very useful. But, let p="Determin whether a given >> > number n is 5". If NPC cannot exclude p in NPC, what is the usefulness >> > of NPC? >> >> You've just explained why it's useful.  It's at the heart of the P/NP >> question -- almost literally.  You hypothesise that "NPC cannot exclude >> p in NPC" but we don't know that.  That's the core of the problem you >> thought you had (or at least claimed to have) solved. > > The problem is: If the problem whether or not p is a NPC cannot be > proved, then all those proofs proving problems, say q, is not NPC must > be false proofs. Because that q must be Ptime reduciable between p. Correct. As of this moment, all purported proofs that "q is not in NPC" are invalid. Any such proof would be of huge significance and would be published with great fanfare. None are known to me at this time. > To be spedific, proving problem p cannot be reduced to problem SAT is obvious > to me. Just by actually programming it, not by abstract deduction, no > info. there. That's fine (though you have the reduction the wrong way round). I have no objection to you being sure of something as yet unproven. -- Ben.