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

Groups > comp.theory > #59368

Re: P!=NP idea

Show all headers | View raw

Mr Flibble <flibble@reddwarf.jmc.corp> writes:

> 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.

I think you just feel the need to say things.  Almost every part of that
is wrong, but I don't think you care.

-- 
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