20100815, 14:17  #34  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·3·311 Posts 
Quote:
I think you need to delete the 'not'.......... 

20100815, 14:40  #35  
Aug 2006
5,981 Posts 
Quote:
Quote:


20100815, 15:19  #36  
"Bob Silverman"
Nov 2003
North of Boston
1110100101000_{2} Posts 
Quote:
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. 

20100815, 16:19  #37  
Aug 2006
5,981 Posts 
Quote:
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:
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 mth bit of the largest prime factor of N?" for 1 < m < lg N. 

20100815, 17:23  #38  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
3×13×293 Posts 
Quote:
To be clear, I believe that P != NP. Paul 

20100815, 20:38  #39  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·3·311 Posts 
Quote:


20100816, 07:12  #40  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
10110010100011_{2} Posts 
Quote:
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 halfway 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 Ptime algorithm. I emphasise that this is not at all rigorous and is almost entirely vigorous handwaving. Turning to PRIMES, the factoring algorithms can still be used but asymptotically better ones have been discovered. ECPP and APRTCL 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 20100816 at 07:57 Reason: Fix a couple of small bugs 

20100816, 07:32  #41 
Aug 2006
5,981 Posts 
Paul, thank you for your carefullyconsidered answer. (And yes, you have understood me correctly in terms of 'probability'  think of it in terms of Bayesian knowledge sets if you must. )

20100817, 06:31  #42 
"Lucan"
Dec 2006
England
2·3·13·83 Posts 
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 
20100817, 12:54  #43 
Aug 2006
5,981 Posts 
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 polynomialtime SAT solver computer.

20100817, 21:37  #44 
"Lucan"
Dec 2006
England
2·3·13·83 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
News  gd_barnes  No Prime Left Behind  257  20220810 06:28 
News  gd_barnes  Conjectures 'R Us  304  20220419 23:07 
Other news  Cruelty  Riesel Prime Search  41  20100308 18:46 
The news giveth, the news taketh away...  NBtarheel_33  Hardware  17  20090504 15:52 
News  KEP  Riesel Base 3 Attack  4  20081217 11:54 