Re^5: Algorithm complexity

I think there are many problems which we don't have efficient algorithms for. There are even some problems to which the known algorithms take so much time that it would be almost impossible for you to get the data needed to plot it and then use numerical methods. One such example are Wiefrich primes for which only 1 pair is known to this date. Can you apply your numerical methods to 1 point on a chart ?

Comment on Re^5: Algorithm complexity

Replies are listed 'Best First'.
Re^6: Algorithm complexity by LanX (Saint) on Jul 08, 2009 at 10:46 UTC
Lets suppose a brute-force algorithm testing all numbers up to n. (don't wanna complicate it by restricting it to primes) After a week and testing 10^x numbers you'll get 2 correct Wieferich primes and the information that calculating a third prime bigger than 10^x takes at least 10^x steps. That's an empiric lower bound for the complexity, you can tell that this brute-force approach is at best O(n) for n<10^x, which is quite accurate! OK, this example is a little bit too trivial, since it's a decision problem. You actually have 10^x points and not only 2 ! Cheers Rolf	[reply]
Re^7: Algorithm complexity by spx2 (Deacon) on Jul 08, 2009 at 11:11 UTC
no you don't . since 1940 until 2005 they have only been able to check all pairs up to 1.25 x 10^15 and it turned out there was only one pair of such numbers . please notice that it took 65 years and they did not find another one , so it's not a matter of weeks/months .. it's almost 7 decades.	[reply]
Re^8: Algorithm complexity by LanX (Saint) on Jul 08, 2009 at 11:27 UTC
Did I say x==15 ??? Does x have to be 15 to suppose it's a hard problem? Please note those "checks" in the referenced article were done with a computer and not with pure mathematical proving! And this computer wasn't build "65 years" ago! Better find another problem this one is a boomerang. 8) Cheers Rolf	[reply]