In computational complexity, we have some proofs that a certain cost is the absolute bare minimum that an optimal solution must expend. We have the same for some mechanical systems too.
If you get the order down to the proven limit, especially for the first time, people sometimes use the word 'perfect', even if there are potentially other solutions with lower constant overhead, or lower practical overhead (see also Timsort, which uses insertion sort for leaf operations).
> Second, in that same paper Schönhage and Strassen conjectured that there should be an even faster algorithm than the one they found — a method that needs only n × log n single-digit operations — and that such an algorithm would be the fastest possible.
Is this saying that there is a proof in there paper that nlogn is the cheapest? If so it certainly beats around the bush.
A conjecture is a proposition that is suspected to be true. So there would be no proof in the paper, but likely some arguments why the authors expect it to be true.
If you get the order down to the proven limit, especially for the first time, people sometimes use the word 'perfect', even if there are potentially other solutions with lower constant overhead, or lower practical overhead (see also Timsort, which uses insertion sort for leaf operations).
> Second, in that same paper Schönhage and Strassen conjectured that there should be an even faster algorithm than the one they found — a method that needs only n × log n single-digit operations — and that such an algorithm would be the fastest possible.
Is this saying that there is a proof in there paper that nlogn is the cheapest? If so it certainly beats around the bush.