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

Groups > comp.theory > #59372

Re: P!=NP idea

Show all headers | View raw

On Thu, 03 Nov 2022 23:50:26 +0000
Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:

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

Not at all: it is you who seems to be fractally wrong on most issues as
evidenced by your claim that Olcott is wrong about the Halting Problem
proofs and your apparent amateurish grasp of hash tables and complexity
analysis.

/Flibble

Back to comp.theory | Previous | Next — Previous 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