Re: Is NPC useless?

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.