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

Groups > comp.theory > #106922 > unrolled thread

Is NPC useless?

Back to article view | Back to comp.theory

Contents

  Is NPC useless? wij <wyniijj5@gmail.com> - 2024-06-11 13:47 +0800
    Re: Is NPC useless? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-11 11:40 +0100
      Re: Is NPC useless? wij <wyniijj5@gmail.com> - 2024-06-11 19:46 +0800
        Re: Is NPC useless? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-12 00:21 +0100
          Re: Is NPC useless? wij <wyniijj5@gmail.com> - 2024-06-12 17:01 +0800
            Re: Is NPC useless? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-12 11:10 +0100

#106922 — Is NPC useless?

NPC specifies a set of very significant problems, and identifies such problems.
So, is very useful. But, let p="Determin whether a given number n is 5". If NPC
cannot exclude p in NPC, what is the usefulness of NPC?

[toc] | [next] | [standalone]

#106934

wij <wyniijj5@gmail.com> writes:

> NPC specifies a set of very significant problems, and identifies such
> problems.  So, is very useful. But, let p="Determin whether a given
> number n is 5". If NPC cannot exclude p in NPC, what is the usefulness
> of NPC?

You've just explained why it's useful.  It's at the heart of the P/NP
question -- almost literally.  You hypothesise that "NPC cannot exclude
p in NPC" but we don't know that.  That's the core of the problem you
thought you had (or at least claimed to have) solved.

-- 
Ben.

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

#106936

On Tue, 2024-06-11 at 11:40 +0100, Ben Bacarisse wrote:
> wij <wyniijj5@gmail.com> writes:
> 
> > NPC specifies a set of very significant problems, and identifies such
> > problems.  So, is very useful. But, let p="Determin whether a given
> > number n is 5". If NPC cannot exclude p in NPC, what is the usefulness
> > of NPC?
> 
> You've just explained why it's useful.  It's at the heart of the P/NP
> question -- almost literally.  You hypothesise that "NPC cannot exclude
> p in NPC" but we don't know that.  That's the core of the problem you
> thought you had (or at least claimed to have) solved.

The problem is: If the problem whether or not p is a NPC cannot be proved, then
all those proofs proving problems, say q, is not NPC must be false proofs.
Because that q must be Ptime reduciable between p.

To be spedific, proving problem p cannot be reduced to problem SAT is obvious
to me. Just by actually programming it, not by abstract deduction, no info. there.

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

#106946

wij <wyniijj5@gmail.com> writes:

> On Tue, 2024-06-11 at 11:40 +0100, Ben Bacarisse wrote:
>> wij <wyniijj5@gmail.com> writes:
>> 
>> > NPC specifies a set of very significant problems, and identifies such
>> > problems.  So, is very useful. But, let p="Determin whether a given
>> > number n is 5". If NPC cannot exclude p in NPC, what is the usefulness
>> > of NPC?
>> 
>> You've just explained why it's useful.  It's at the heart of the P/NP
>> question -- almost literally.  You hypothesise that "NPC cannot exclude
>> p in NPC" but we don't know that.  That's the core of the problem you
>> thought you had (or at least claimed to have) solved.
>
> The problem is: If the problem whether or not p is a NPC cannot be
> proved, then all those proofs proving problems, say q, is not NPC must
> be false proofs.  Because that q must be Ptime reduciable between p.

Correct.  As of this moment, all purported proofs that "q is not in NPC"
are invalid.  Any such proof would be of huge significance and would be
published with great fanfare.  None are known to me at this time.

> To be spedific, proving problem p cannot be reduced to problem SAT is obvious
> to me. Just by actually programming it, not by abstract deduction, no
> info. there.

That's fine (though you have the reduction the wrong way round).  I have
no objection to you being sure of something as yet unproven.

-- 
Ben.

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

#106975

On Wed, 2024-06-12 at 00:21 +0100, Ben Bacarisse wrote:
> wij <wyniijj5@gmail.com> writes:
> 
> > On Tue, 2024-06-11 at 11:40 +0100, Ben Bacarisse wrote:
> > > wij <wyniijj5@gmail.com> writes:
> > > 
> > > > NPC specifies a set of very significant problems, and identifies such
> > > > problems.  So, is very useful. But, let p="Determin whether a given
> > > > number n is 5". If NPC cannot exclude p in NPC, what is the usefulness
> > > > of NPC?
> > > 
> > > You've just explained why it's useful.  It's at the heart of the P/NP
> > > question -- almost literally.  You hypothesise that "NPC cannot exclude
> > > p in NPC" but we don't know that.  That's the core of the problem you
> > > thought you had (or at least claimed to have) solved.
> > 
> > The problem is: If the problem whether or not p is a NPC cannot be
> > proved, then all those proofs proving problems, say q, is not NPC must
> > be false proofs.  Because that q must be Ptime reduciable between p.
> 
> Correct.  As of this moment, all purported proofs that "q is not in NPC"
> are invalid.  Any such proof would be of huge significance and would be
> published with great fanfare.  None are known to me at this time.
> 
> > To be spedific, proving problem p cannot be reduced to problem SAT is obvious
> > to me. Just by actually programming it, not by abstract deduction, no
> > info. there.
> 
> That's fine (though you have the reduction the wrong way round).  I have
> no objection to you being sure of something as yet unproven.
> 

The Proof2 above was removed (flawed), because it still relies on the previous proof 
but adds confusion:

------------------------
This file is intended a proof that ℙ≠ℕℙ. The contents may be updated anytime.
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
...[cut]
Prop1: ANP problem can be divided into two size-1-subproblems.
   Proof: By spliting the certificate as follow:
          bool temp_anp(Problem q) {
            if(q.certificate().size()<Thresh) { // Thresh is a small constant
              return solve_thresh_case(q);
            }
            Problem q1,q2;
            split_certificate(q,q1,q2);        // Split the certificate in q
            return temp_anp(q1) || temp_anp(q2); // to form q1,q2
          }

Prop2: ℙ≠ℕℙ
   Proof: The temp_anp(q) can be re-written as follow:
          bool temp_anp(Problem q) {
            if(q.certificate().size()<Thresh) { // Thresh is a small constant
              return solve_thresh_case(q);
            }
            Problem q1,q2;
            split_certificate(q,q1,q2);  // Split the certificate in q to
                                         //   disjoint subproblem q1, q2.
            Info I;                      // I=info. that helps solving q
            if(temp_anp_i(q1,I)==true) { // temp_anp_i(q1,I) solves temp_anp(q1)
                                         // and stores whatever helpful into I
              return true;
            }
            return solv_remain(q2,I);    // Solve temp_anp(q2) with the given I
          }

          For a ℕℙℂ problem q, if ℙ=ℕℙ, then information I is unnecessary for
          solv_remain(q2,I) because it can compute I in Ptime by its own. Thus,
          the complexity of solv_remain(..) is equivalent to the independent
          size-1-subproblem temp_anp(q2) (if not equivalent, the general
          recursive algorithms of solving ℕℙℂ and Prop1 are wrong, which is not
          the fact). Equally, temp_anp_i(q1,I) is then equivalent to the
          size-1-subproblem temp_anp(q1) simply by not providing I. Therefore,
          the complexity of temp_anp(q) is W(|q|)= W(|q|-1)+W(|q|-1)=
          2^(|q|-1)*W(1), W(1)>=1, a O(2^N) level of complexity contradicting
          the assumed Ptime. Therefore, from ℕℙℂ≠ℙ, we can conclude ℙ≠ℕℙ.
-----------------------------------------------------------------------------

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

#106976

wij <wyniijj5@gmail.com> writes:

> On Wed, 2024-06-12 at 00:21 +0100, Ben Bacarisse wrote:
>> wij <wyniijj5@gmail.com> writes:
>> 
>> > On Tue, 2024-06-11 at 11:40 +0100, Ben Bacarisse wrote:
>> > > wij <wyniijj5@gmail.com> writes:
>> > > 
>> > > > NPC specifies a set of very significant problems, and identifies such
>> > > > problems.  So, is very useful. But, let p="Determin whether a given
>> > > > number n is 5". If NPC cannot exclude p in NPC, what is the usefulness
>> > > > of NPC?
>> > > 
>> > > You've just explained why it's useful.  It's at the heart of the P/NP
>> > > question -- almost literally.  You hypothesise that "NPC cannot exclude
>> > > p in NPC" but we don't know that.  That's the core of the problem you
>> > > thought you had (or at least claimed to have) solved.
>> > 
>> > The problem is: If the problem whether or not p is a NPC cannot be
>> > proved, then all those proofs proving problems, say q, is not NPC must
>> > be false proofs.  Because that q must be Ptime reduciable between p.
>> 
>> Correct.  As of this moment, all purported proofs that "q is not in NPC"
>> are invalid.  Any such proof would be of huge significance and would be
>> published with great fanfare.  None are known to me at this time.
>> 
>> > To be spedific, proving problem p cannot be reduced to problem SAT
>> > is obvious
>> > to me. Just by actually programming it, not by abstract deduction, no
>> > info. there.
>> 
>> That's fine (though you have the reduction the wrong way round).  I have
>> no objection to you being sure of something as yet unproven.
>> 
>
> The Proof2 above was removed (flawed), because it still relies on the
> previous proof  but adds confusion:
>
> ------------------------
> This file is intended a proof that ℙ≠ℕℙ. The contents may be updated anytime.
> https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
> ...[cut]
> Prop1: ANP problem can be divided into two size-1-subproblems.
>    Proof: By spliting the certificate as follow:
>           bool temp_anp(Problem q) {
>             if(q.certificate().size()<Thresh) { // Thresh is a small constant
>               return solve_thresh_case(q);
>             }
>             Problem q1,q2;
>             split_certificate(q,q1,q2);        // Split the certificate in q
>             return temp_anp(q1) || temp_anp(q2); // to form q1,q2
>           }
>
> Prop2: ℙ≠ℕℙ
>    Proof: The temp_anp(q) can be re-written as follow:
>           bool temp_anp(Problem q) {
>             if(q.certificate().size()<Thresh) { // Thresh is a small constant
>               return solve_thresh_case(q);
>             }
>             Problem q1,q2;
>             split_certificate(q,q1,q2);  // Split the certificate in q to
>                                          //   disjoint subproblem q1, q2.
>             Info I;                      // I=info. that helps solving q
>             if(temp_anp_i(q1,I)==true) { // temp_anp_i(q1,I) solves temp_anp(q1)
>                                          // and stores whatever helpful into I
>               return true;
>             }
>             return solv_remain(q2,I);    // Solve temp_anp(q2) with the given I
>           }
>
>           For a ℕℙℂ problem q, if ℙ=ℕℙ, then information I is unnecessary for
>           solv_remain(q2,I) because it can compute I in Ptime by its own. Thus,
>           the complexity of solv_remain(..) is equivalent to the independent
>           size-1-subproblem temp_anp(q2) (if not equivalent, the general
>           recursive algorithms of solving ℕℙℂ and Prop1 are wrong, which is not
>           the fact). Equally, temp_anp_i(q1,I) is then equivalent to the
>           size-1-subproblem temp_anp(q1) simply by not providing I. Therefore,
>           the complexity of temp_anp(q) is W(|q|)= W(|q|-1)+W(|q|-1)=
>           2^(|q|-1)*W(1), W(1)>=1, a O(2^N) level of complexity contradicting
>           the assumed Ptime. Therefore, from ℕℙℂ≠ℙ, we can conclude ℙ≠ℕℙ.
> -----------------------------------------------------------------------------

You are missing any step that allows one to conclude that ℙ≠ℕℙ.  What
you appear to be proving (that from ℕℙℂ≠ℙ, we can conclude ℙ≠ℕℙ) is a
known theorem, but there are much simpler ways to show it.

-- 
Ben.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.theory

csiph-web