Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #106936

Re: Is NPC useless?

Show all headers | View raw

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.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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