Loading ...
Sorry, an error occurred while loading the content.

P or NP?

Expand Messages
  • Kermit Rose
    P or NP? Suppose you could prove: that for each positive odd integer, z, between 2^3 and 2^4, there existed an algorithm4 which depends only on the base 2
    Message 1 of 2 , Feb 7, 2014
    • 0 Attachment
      P or NP?

      Suppose you could prove:

      that for each positive odd integer, z, between 2^3 and 2^4,
      there existed an algorithm4 which
      depends only on the base 2 representation of z,
      and returns every pair of factors of z;

      that for each positive odd integer, z, between 2^4 and 2^5,
      there existed an algorithm5 which
      is more complex than algorithm4,
      depends only on the base 2 representation of z,
      and returns every pair of factors of z;

      that for each positive odd integer, z, between 2^5 and 2^6,
      there existed an algorithm6 which
      is more complex than algorithm5,
      depends only on the base 2 representation of z,
      and returns every pair of factors of z;

      etc.

      Sometimes the complexity of the next algorithm up
      for the next higher power of 2
      is more than double the current algorithm.

      Which language would you use for this situation?

      Would you say:
      (1) Factoring is in P, but no polynomial time factoring algorithm is
      practical.

      or

      (2) Factoring is in NP because the polynomial time factoring algorithm
      complexity
      increases with increase in power of 2.

      ???


      each increase in power of 2.
    • djbroadhurst
      ... Your next algorithm seems to be needed when the target doubles, i.e when the number of bits increases by 1. You say this costs more than double. So the
      Message 2 of 2 , Feb 7, 2014
      • 0 Attachment

        Kermit Rose wrote:


        > Sometimes the complexity of the next algorithm up
        > for the next higher power of 2
        > is more than double the current algorithm.


        Your "next algorithm" seems to be needed when the target
        doubles, i.e when the number of bits increases by 1.
        You say this costs more than double.
        So the cost is (at least) exponential in the number of bits;
        certainly not polynomial.

        David
      Your message has been successfully submitted and would be delivered to recipients shortly.