Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #106946
| From | Ben Bacarisse <ben@bsb.me.uk> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Is NPC useless? |
| Date | 2024-06-12 00:21 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87msnr12x9.fsf@bsb.me.uk> (permalink) |
| References | <296ed519c7d2c9bfac06dc145f40fbabf765a3be.camel@gmail.com> <877cev3gpz.fsf@bsb.me.uk> <8ede5c7eb5a672de9bdaea8e7e4d038a8abc5194.camel@gmail.com> |
wij <wyniijj5@gmail.com> writes: > On Tue, 2024-06-11 at 11:40 +0100, Ben Bacarisse wrote: >> wij <wyniijj5@gmail.com> 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.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Is NPC useless? wij <wyniijj5@gmail.com> - 2024-06-11 13:47 +0800
Re: Is NPC useless? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-11 11:40 +0100
Re: Is NPC useless? wij <wyniijj5@gmail.com> - 2024-06-11 19:46 +0800
Re: Is NPC useless? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-12 00:21 +0100
Re: Is NPC useless? wij <wyniijj5@gmail.com> - 2024-06-12 17:01 +0800
Re: Is NPC useless? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-12 11:10 +0100
csiph-web