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

Groups > comp.theory > #59365 > unrolled thread

P!=NP idea

Back to article view | Back to comp.theory

Contents

  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

#59365 — P!=NP idea

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.

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?

[toc] | [next] | [standalone]

#59366

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.

[toc] | [prev] | [next] | [standalone]

#59367

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

[toc] | [prev] | [next] | [standalone]

#59368

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.

[toc] | [prev] | [next] | [standalone]

#59371

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 you apparent amateurish grasp of hash tables and complexity
analysis.

/Flibble

[toc] | [prev] | [next] | [standalone]

#59372

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.theory

csiph-web