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

Groups > comp.theory > #59367

Re: P!=NP idea

Show all headers | View raw

On Thu, 03 Nov 2022 15:45:22 +0000
Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:

> wij <wyniijj5@gmail.com> writes:
> 
> > The idea was formed while I was learning complexity theory many
> > years ago, and recalled to me by the Halting Problem. 
> >
> > Q: Given a password checker function "bool pchk(const char* psw)",
> > a program f can only call pchk with guess-password. What is the
> > complexity of f to find out the password of pchk?
> > A: 'Obviously', the complexity of f is O(2^n). Therefore, f∈NP and
> > f∉P. QED.  
> 
> P and NP are classes of problems, not programs.  f, a program, can't
> be ∈ or ∉ either of them!
> 
> > I was not sure of such an idea, because I did not like to read
> > 'theory' and the idea seemed too simple. So, any problem with such
> > an idea as a PNP proof?  
> 
> What you are left with (if you work our the detailed described below)
> is a problem for which you can't see a polynomial-time solution.
> There are lots of these, but they don't constitute a proof.
> 
> There are a lot of messy details that I've glossed over.  "Finding a
> password" is not a properly defined problem.  Everything has to be
> made explicit for it to be a well-defined problem.  For example, you
> could say "given (as input) an SHA1 hash value, find a string that
> hashes to that value.  Well that has a constant-time solution!  Can
> you see why, and can you see how to change the problem so it really
> looks like the best algorithm one can image is exponential in time?

The constant time solution you speak of may not be practical on extant
computing hardware if you have transformed the problem into having a
greater space complexity beyond the capabilities of the machine.

/Flibble

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

Thread

P!=NP idea wij <wyniijj5@gmail.com> - 2022-11-03 05:03 -0700
  Re: P!=NP idea Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-03 15:45 +0000
    Re: P!=NP idea Mr Flibble <flibble@reddwarf.jmc.corp> - 2022-11-03 19:17 +0000
      Re: P!=NP idea Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-03 23:50 +0000
        Re: P!=NP idea Mr Flibble <flibble@reddwarf.jmc.corp> - 2022-11-04 13:58 +0000
        Re: P!=NP idea Mr Flibble <flibble@reddwarf.jmc.corp> - 2022-11-04 13:59 +0000

csiph-web