English Language & Usage Stack Exchange is a question and answer site for linguists, etymologists, and serious English language enthusiasts. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What does provably good mean ? Does it mean not good for practical scenario and only good theoretically ?

None of the hash functions that we would be discussing in today's lecture are provably good hash functions .

I see it here at 39:06 time line.

share|improve this question

closed as too localized by Kris, TimLymington, MετάEd, Mahnax, tchrist Aug 26 '12 at 15:21

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

Are you sure it is "None ... not"? Seems that was not intended. – Kris Aug 17 '12 at 10:56
I would myself write that as "Among the hash functions that we would be discussing in today's lecture, none is provably good." – Kris Aug 17 '12 at 11:11
NMF - but I'd guess that in this case "provably" means just the opposite: that none of the functions can be shown to be "good" by formal mathematical analysis. What canons of proof does the course follow? – StoneyB Aug 17 '12 at 11:21
@StoneyB Yes, I agree, but in isolation it’s difficult to see quite how it would be used ... – Elberich Schneider Aug 17 '12 at 12:07
up vote 5 down vote accepted

To say that something is "provably X" means that you can prove that it is, indeed, X. That is, if you say, "X is true", it may be a statement of opinion, or you may mean that you suspect that it is true, or you think it is probably true, but you haven't gone to any great efforts to verify it. But if you say "X is provably true", you mean that there is concrete evidence.

In this case, if someone said, "The Smith Transform is a good hash function", he might simply mean that he read the code and it looked good, or he tried it a couple of times and it appeared to work well. But if he says, "The Smith Transform is a provably good hash function", that indicates that some sort of mathematical analysis has been done, or perhaps an extensive empirical analysis, to prove that it really does give an even distribution of hash values or whatever the criteria are for a "good hash function".

share|improve this answer
In context - a lecturer adding an off-the-cuff remark to a presentation which is structured but not scripted - this is probably exactly what is meant: that none of the functions has been proven by mathematical or practical analysis to be good. In more formal contexts, however, "None . . . is provably good" implies that no such proof is possible within the applicable canons. – StoneyB Aug 17 '12 at 14:42
@StoneyB, I think in this case the lecturer was precisely right because the methods under discussion (apparently §12.3.1,2 in Cormen et al) miss out on a couple of desired properties, such as cryptographic strength and avalanching. – jwpat7 Aug 18 '12 at 9:16
@jwpat7 NMF, as I said above. But what you seem to be saying is that the functions are provably not good, which is not quite the same thing. – StoneyB Aug 18 '12 at 11:50
@StoneyB Well, it's possible that some hash functions are provably good, but no one has subjected these particular functions to the required analysis. – Jay Aug 20 '12 at 13:44
@jwpat7 I'm not sure exactly what it means for a hash function to have "cryptographic strength", or why anything to do with cryptography would be a criteria for a good hash function. Before we discuss whether a function is a good hash function, I guess we have to agree what the criteria are. But that's clearly not an "English" discussion but a computer algorithms discussion, so I won't pursue it any further here. – Jay Aug 20 '12 at 13:47

Please correct me if I misunderstood your question but according to a Google search:

(provably) demonstrably: in an obvious and provable manner; "his documentary sources are demonstrably wrong"


And so, it cannot be demonstrated that most of the discussed hash functions that day are good, as no such, satisfying proof exists.

share|improve this answer
Your edit is not correct. The original sentence makes proper sense. – Kris Aug 17 '12 at 10:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.