## P or NP?

Expand Messages
• 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.
• ... 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.