4 ms·
Can you explain that further? A random oracle is a random set of strings...?
by SilasX 10y ago
Can you explain that further? A random oracle is a random set of strings...?
- tromp 10y agoFlip a coin for each string to decide its membership in the language. In other words, let the characteristic sequence of the language be an infinite random binary string.
- SilasX 10y agoSo, a language is a mapping from strings to 1/0? And an oracle is a language?
- kosievdmerwe 10y agoA language is a set of strings and an oracle for that language answers whether a certain string is in that language in O(1) time.