T.Madry - 6 months ago 32

Python Question

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.