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
#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'}...?

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.

Source (Stackoverflow)