Opponents argument for finding n-bit strings
Given:
S, an odd set of n-bit strings
A, a specific n-bit string
show that any algorithm that decides if A is in S must check all n bits of A in the worst case.
Usually, of course, we expect to see all parts of the string to match, but there is something special about S being odd in size, which eludes me.
source to share
Let's say we have an algorithm A that correctly determines the membership of S and says, for any input n-bit string, whether the string is in S or not.
Suppose that for a given input n-bit string s1, Algorithm A never looks at bit i s1 and continues to say "s1 is in (not in) S". Then the string s2 equal to s1, except the bit I flipped, is also in (not in) S! That is, for any line that we feed to A, if A does not look at a specific bit, that is, the second line is also in (or not in) S with the bit flipped.
Then what is special about the odd sets S? We cannot uniformly concatenate strings in S. That is, there must be a string s3 that A looks at and decides, is in S, for which no bit can be flipped to form another string in S. Thus, A must look to all bits of s3 (otherwise we could have made such a string as we did before).
source to share
I think the odd number key is to find the end of your set or array in memory
.
Suppose you are using a bit system 32
, perhaps the compiler aligns the structural data of your program in memory on eight byte boundaries. There is a whole load of pointers per row in your data segment. If there are an odd number of lines, the next thing that needs eight-byte alignment has four padding bytes in front of it. If there is an even number of lines, there is no indentation.
source to share
If I understand this correctly, it doesn't matter if S has an odd or even number of rows. For any particular string in S, to check that it matches an arbitrary string A, you must check every character in every one. You can stop earlier if any line is shorter than another or the character you are checking does not match.
source to share