0

Could somebody comment on the conjecture stated in the title:

"abc-conjecture ( http://en.wikipedia.org/wiki/Abc_conjecture ) follows from the (prime-factorization is NP), see http://en.wikipedia.org/wiki/Integer_factorization or http://en.wikipedia.org/wiki/Shor's_algorithm )"

Or may be help with examples of similar claims, relating statements from Computer Science and Number theory.

flag
5 
 Without an argument, this is just idle speculation, not a conjecture. I voted to close. – Andy Putman Aug 23 2010 at 21:08
5 
 Is there any reason to think the two questions (abc and difficulty of prime factorization) are related? – Emerton Aug 23 2010 at 21:11
1 
 An interesting connection between number theory and computer science is that if you could compute the Busy Beaver function for reasonably large n, you could prove Goldbach's conjecture, among other things, as noted in en.wikipedia.org/wiki/Busy_beaver. – Eric Tressler Aug 23 2010 at 21:35
1 
 @Andy: I'm aware of this. Still, I consider it an interesting kind of barrier to proof. – Eric Tressler Aug 23 2010 at 21:51
2 
 PS: Three nitpicks. (1) NP refers to decision problems, which factorization is not. There are lots of standard ways to fix this, and I plan to gloss over the issue myself. (2) You probably mean NP-complete. See Wikipedia for the distinction. (3) Many computational number-theorists believe that factorization is unlikely to be NP-complete. If so, your conjecture would be vacuously true, as anything follows from a falsehood. – David Speyer Aug 23 2010 at 23:06
show 5 more comments

closed as not a real question by Robin Chapman, Andy Putman, Qiaochu Yuan, Felipe Voloch, Steve Huntsman Aug 23 2010 at 23:13

Browse other questions tagged or ask your own question.