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

Groups > comp.theory > #59366

Re: P!=NP idea

Show all headers | View raw

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?

-- 
Ben.

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