mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2010-08-15, 14:17   #34
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23·3·311 Posts
Default

Quote:
Originally Posted by xilman View Post
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'..........
R.D. Silverman is offline   Reply With Quote
Old 2010-08-15, 14:40   #35
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,981 Posts
Default

Quote:
Originally Posted by xilman View Post
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?
CRGreathouse is online now   Reply With Quote
Old 2010-08-15, 15:19   #36
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

11101001010002 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2010-08-15, 16:19   #37
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,981 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
CRGreathouse is online now   Reply With Quote
Old 2010-08-15, 17:23   #38
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

3×13×293 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
xilman is offline   Reply With Quote
Old 2010-08-15, 20:38   #39
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23·3·311 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2010-08-16, 07:12   #40
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

101100101000112 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
xilman is offline   Reply With Quote
Old 2010-08-16, 07:32   #41
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,981 Posts
Default

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. )
CRGreathouse is online now   Reply With Quote
Old 2010-08-17, 06:31   #42
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Quote:
Originally Posted by Batalov View Post
...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
davieddy is offline   Reply With Quote
Old 2010-08-17, 12:54   #43
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,981 Posts
Default

Quote:
Originally Posted by davieddy View Post
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.
CRGreathouse is online now   Reply With Quote
Old 2010-08-17, 21:37   #44
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
davieddy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
News gd_barnes No Prime Left Behind 257 2022-08-10 06:28
News gd_barnes Conjectures 'R Us 304 2022-04-19 23:07
Other news Cruelty Riesel Prime Search 41 2010-03-08 18:46
The news giveth, the news taketh away... NBtarheel_33 Hardware 17 2009-05-04 15:52
News KEP Riesel Base 3 Attack 4 2008-12-17 11:54

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


Mon Aug 15 21:55:23 UTC 2022 up 39 days, 16:42, 1 user, load averages: 1.74, 1.30, 1.24

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”