1. Forum
  2. Usenet
  3. COMP.THEORY

  • Re: How to prove q is not NPC?

    From Ben Bacarisse@21:1/5 to wij on Mon Jul 29 00:22:15 2024
    wij <[email protected]> writes:

    Problem q: Given a number n, determine whether n is 5 or not.
    What is the VALID proof that q∉NPC?

    What makes you think there is one?

    What makes you think that someone who had such a proof would waste time
    posting it here rather than publishing in the CACM?

    What was wrong with the answers you got the last time you asked this?

    --
    Ben.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Andy Walker@21:1/5 to wij on Tue Jul 30 14:52:52 2024
    On 30/07/2024 14:30, wij wrote:
    On Tue, 2024-07-30 at 20:29 +0800, wij wrote: [...]
    On Mon, 2024-07-29 at 07:00 +0800, wij wrote: [...]
    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?

    Did you not understand the answers you have previously had from
    Ben and me, and possibly others I've forgotten [sorry if so]? Categories
    such as NPC, NP-hard, ... are "interesting" only if P /= NP. If you can
    prove /that/, then don't waste time here, fame and fortune await.

    --
    Andy Walker, Nottingham.
    Andy's music pages: www.cuboid.me.uk/andy/Music
    Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Kinross

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)