Re: Is NPC useless?

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.

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.