P!=NP in the news

[R.D. Silverman]

Originally Posted by xilman

AFAIK, the general consensus is that it unlikely that P and NP are not equal. However, the general consensus has been wrong on numerous occasions in the past.

FWIW, my guess is that P !=NP but that there is a fair chance that integer factorization is in P.


Paul

Huh? Read what you wrote: "unlikely that P and NP are not equal"

I think you need to delete the 'not'..........

[CRGreathouse]

Originally Posted by xilman

FWIW, my guess is that P !=NP but that there is a fair chance that integer factorization is in P.

Interesting... Peter Shor said the same thing recently:

[Q: Is integer factorization outside of P?]

I have to say that this isn't clear either way.

Is this the general consensus?

[R.D. Silverman]

Originally Posted by CRGreathouse

Interesting... Peter Shor said the same thing recently:


Is this the general consensus?

A minor nitpick.

The definition/wording in Wikipaedia is a bit vague:

"given an integer N and an integer M with 1 ≤ M ≤ N, does N have a factor d with 1 < d < M?"

If I give you M = [sqrt(N)] + 1, the answer is trivially yes. (or N is prime;
which is in P)

If M ~ (log(N))^k for any k, then the question can be answered
in polynomial time.

The meaning of "an integer M", is unclear, because it is clear that
for some M depending on N the question is in P.

[CRGreathouse]

Originally Posted by R.D. Silverman

The meaning of "an integer M", is unclear, because it is clear that
for some M depending on N the question is in P.

I don't really think so. The question is, in terms of N only, what is the worst-case complexity of determining whether there is a factor between 1 and M?

Sure, there are easy cases, but there are easy cases of SAT, too.


So what's your view? How likely is it that FACTORIZATION is in P? (xilman, you're welcome to answer as well!) And if you're willing to go out on a limb, how likely to you think it is that:

• integer factorization can be performed in time for any ?
• integer factorization can be performed in half-exponential time, ?
• the appropriate decision version of integer factorization* is in BPP (or even RP)?

I would have called all of these extremely unlikely, but now that I'm seeing people suggest that FACTORIZATION might be in P it seems like these should be reconsidered (since they are 'at least as likely').

* Either the one you gave above, or, say, "What is the m-th bit of the largest prime factor of N?" for 1 < m < lg N.

[xilman]

Originally Posted by R.D. Silverman

Huh? Read what you wrote: "unlikely that P and NP are not equal"

I think you need to delete the 'not'..........

Thanks for picking up this error. You are quite correct and I somehow managed to get lost among the repeated negatives.

To be clear, I believe that P != NP.

Paul

[R.D. Silverman]

Originally Posted by CRGreathouse

I don't really think so. The question is, in terms of N only, what is the worst-case complexity of determining whether there is a factor between 1 and M?

Sure, there are easy cases, but there are easy cases of SAT, too.


So what's your view? How likely is it that FACTORIZATION is in P? (xilman, you're welcome to answer as well!) And if you're willing to go out on a limb, how likely to you think it is that:

• integer factorization can be performed in time for any ?
• integer factorization can be performed in half-exponential time, ?
• the appropriate decision version of integer factorization* is in BPP (or even RP)?

I would have called all of these extremely unlikely, but now that I'm seeing people suggest that FACTORIZATION might be in P it seems like these should be reconsidered (since they are 'at least as likely').

* Either the one you gave above, or, say, "What is the m-th bit of the largest prime factor of N?" for 1 < m < lg N.

I have no idea if factors is in P. Insufficient information.

[xilman]

Originally Posted by CRGreathouse

So what's your view? How likely is it that FACTORIZATION is in P? (xilman, you're welcome to answer as well!)

First off, let me say that assigning a probability in the mathematical sense is not well defined. The proposition is either true or false.

However, we could define it in another way, that used by gamblers who are not mathematicians. The probability is then the answer to the question: if you wished to place a bet, what odds would you negotiate before committing your money? My gut reaction, and it is only that, is that I'd settle for odds somewhere between 100:1 and 1000:1. That is a "fair chance" in my estimation.

The reasoning behind my estimation that FACTORIZATION has a fair chance of being in P is entirely the result of analogy and wishful thinking. I don't know the answer --- which is pretty clear because you would have heard about it if I did. Anyway, history shows us that until recently factorization was as hard as primality proving and only exponential time algorithms were known for each. About forty years ago, the two problems were still of equal complexity but a subexponential algorithm was found for factoring. Dixon's algorithm, for instance, takes time which is in a loose sense half-way between exponential and polynomial. The looseness can be removed but I won't bother in this post. A decade or so later, GNFS factors in (heuristic) 1/3 exponential -- 2/3 polynomial time, again in the same loose sense. By that measure, we're already 2/3 of the way to finding a P-time algorithm. I emphasise that this is not at all rigorous and is almost entirely vigorous hand-waving.

Turning to PRIMES, the factoring algorithms can still be used but asymptotically better ones have been discovered. ECPP and APRT-CL both run in (heuristically for ECPP) very nearly polynomial time. A few years ago, the polynomial time AKS algorithm was discovered.


Paul

[CRGreathouse]

Paul, thank you for your carefully-considered answer. (And yes, you have understood me correctly in terms of 'probability' -- think of it in terms of Bayesian knowledge sets if you must. )

[davieddy]

Originally Posted by Batalov

...well at least now his life is still pointful.

But nobody (except Xilman miscounting negatives) was trying
to suggest P = NP.

I quoted Paul Seymour because I thought others here might
find his criteria for plausibility (long and unintelligible) hilarious,
especially coming from the chief editor of a major mathematical journal.
(More or less the same as Bob's initial reaction).

OTOH, the statement that P=NP would make much of his
mathematical life pointless conveys the importance of the
problem. Can someone explain simply why he said that?

David

[CRGreathouse]

Originally Posted by davieddy

OTOH, the statement that P=NP would make much of his
mathematical life pointless conveys the importance of the
problem. Can someone explain simply why he said that?

Not that I agree with the sentiment, but I think the theory is that if P = NP, proving theorem is easy, so who needs a mathematician? Just hook up the polynomial-time SAT solver computer.

[davieddy]

Originally Posted by CRGreathouse

Not that I agree with the sentiment, but I think the theory is that if P = NP, proving theorem is easy, so who needs a mathematician? Just hook up the polynomial-time SAT solver computer.

Hmm. Sometimes my eyes just glaze over.
(Just ask William)

David