T.Madry T.Madry - 2 months ago 13
Python Question

What's The Mapping Reduction Function

This is (I think) easy problem from Complexity Theory.

#Consider the language E over the binary alphabet
#consisting of strings representing even non-negative
#integers (with leading zeros allowed).
#I.e. E = {x | x[-1] == '0'}.
#
#Reduce E to the language {'Even'} by implementing
#the function R
def R(x):
#Code


def main():
#test cases
assert(R('10010') in ['Even'])
assert(R('110011') not in ['Even'])

if __name__ == '__main__':
main()


According to Mapping Reduction def:

"Language A is mapping reducible to language B, written A ≤ mB,
if there is a computable function f : Σ ∗ −→Σ ∗ , where for every w,
w ∈ A ⇐⇒ f (w) ∈ B.
The function f is called the reduction from A to B."

A computable mapping function would be f(n) = 2n (or x << y in Python), but in that case, those assertions doesn't make sense, because every R(x) should be in {'Even'}...?

Answer

So basically you have E as the binary representations of integers, even numbers only. This is indicated by the last digit (integer 1) being 0. All other digits represent multiples of 2 and therefore do not matter.

The target "language" consists just of the string "Even". That is, every even number must map to the word "Even".

So the assignment is practically: if x represents an even binary number, return "Even", otherwise return something else.

The most straightforward way is to check the definition of an even binary number:

def R(x):  # shortest/fastest option
    return 'Even' if x[-1] == 0 else ''

def Rdocs(x):
    """
    Map any of {x | x[-1] == '0'} to {'Even'}

    Uses the definition {x | x[-1] == '0'}
    """
    if x[-1] == '0':  # check that x satisfies definition of even binary
        return 'Even'
    return ''

One can also do this with an explicit mapping:

translate = {'0': 'Even', '1': ''}
def Rmap(x, default=''):
    """
    Map any of {x | x[-1] == '0'} to {'Even'}

    Uses a literal mapping of x[-1]
    """
    return translate[x[-1]]

Alternatively, you can convert the binary to a number. Python's int type also takes binary literals:

def Rbin(x):
    """
    Map any of {x | x[-1] == '0'} to {'Even'}

    Uses python builtin to evaluate binary
    """
    return '' if int(x, 2) % 2 else 'Even'

I guess technically speaking, R(x) should be only defined for every x in {x | x[-1] == '0'}, unless you assume the empty word is implicitly contained in every language. Your unit tests suggest it must return something, however. You may want to return 'Odd' or None instead of the empty word.

Comments