mersenneforum.org P!=NP in the news
 Register FAQ Search Today's Posts Mark Forums Read

2010-08-15, 14:17   #34
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·5·373 Posts

Quote:
 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'..........

2010-08-15, 14:40   #35
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 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:
Quote:
 [Q: Is integer factorization outside of P?] I have to say that this isn't clear either way.
Is this the general consensus?

2010-08-15, 15:19   #36
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·5·373 Posts

Quote:
 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.

2010-08-15, 16:19   #37
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 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 $N^\varepsilon$ for any $\varepsilon>0$?
• integer factorization can be performed in half-exponential time, $f(f(x))=\exp(x)$?
• 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.

2010-08-15, 17:23   #38
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2C7A16 Posts

Quote:
 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

2010-08-15, 20:38   #39
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·5·373 Posts

Quote:
 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 $N^\varepsilon$ for any $\varepsilon>0$? integer factorization can be performed in half-exponential time, $f(f(x))=\exp(x)$? 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.

2010-08-16, 07:12   #40
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2×5,693 Posts

Quote:
 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

Last fiddled with by xilman on 2010-08-16 at 07:57 Reason: Fix a couple of small bugs

 2010-08-16, 07:32 #41 CRGreathouse     Aug 2006 10111010110112 Posts 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. )
2010-08-17, 06:31   #42
davieddy

"Lucan"
Dec 2006
England

2·3·13·83 Posts

Quote:
 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

2010-08-17, 12:54   #43
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 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.

2010-08-17, 21:37   #44
davieddy

"Lucan"
Dec 2006
England

2·3·13·83 Posts

Quote:
 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.

David

 Similar Threads Thread Thread Starter Forum Replies Last Post gd_barnes No Prime Left Behind 255 2022-06-01 00:03 gd_barnes Conjectures 'R Us 304 2022-04-19 23:07 Cruelty Riesel Prime Search 41 2010-03-08 18:46 NBtarheel_33 Hardware 17 2009-05-04 15:52 KEP Riesel Base 3 Attack 4 2008-12-17 11:54

All times are UTC. The time now is 21:20.

Tue Jul 5 21:20:45 UTC 2022 up 82 days, 19:22, 0 users, load averages: 1.73, 1.39, 1.36