Sujet : Re: How to prove q is not NPC?
De : wyniijj5 (at) *nospam* gmail.com (wij)
Groupes : comp.theoryDate : 30. Jul 2024, 14:30:56
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <15c597b7393b57be4408e4e7d6948bb42245af95.camel@gmail.com>
References : 1 2
User-Agent : Evolution 3.50.2 (3.50.2-1.fc39)
On Tue, 2024-07-30 at 20:29 +0800, wij wrote:
On Mon, 2024-07-29 at 07:00 +0800, wij wrote:
Problem q: Given a number n, determine whether n is 5 or not.
What is the VALID proof that q∉NPC?
!!! This is a challenging question !!!
Let's change the question a bit.
How do you prove q is not a NPC problem?
Or, How do you prove the problem "determine whether n is 5" is not a NP-hard problem?
If these cannot be proven, what the computation theory is really doing?
How to prove q is not NPC?
Re: How to prove q is not NPC?
