Life Outside PLT1

28th June

July 30, 2008 on 9:16 pm | In Code | | Jeremy Read

Watched a world war two doco, it’s interesting. Watch it.

Another game for you to enjoy: Noodles

Up/Down/Left/Right for movement. R restarts the level. There’s only eight levels.

I’ll post the source code for you later.

CS750 Notes:

RELPRIME = { <x,y> | x and y are relatively prime }

Theorem REPRIME ∈ P

Proof: To show Euclid’s GCD algorithm is in P , this suffices  since x and y are relatively prime iff GCD(x,y) = 1

Algorithm:

Input <x,y> where x,y are binary non-negative integers

If y = 0 return x

Else return GCD(y, x mod y)

Example: GCD(26,38)

GCD(26,38) = GCD(38, 26 mod 38)
GCD(38, 26) = GCD(26, 38 mod 26)
GCD(26, 12) = GCD(12, 26 mod 12)
GCD(12,2) = GCD(2, 12 mod 2)
GCD(2,0) = 2

=> not relatively prime

Proof: Need to show there are O(poly(lg (x * y ) ) recursive calls since inpute size is lg x + lg y

Note after first call to GCD assigns x > y

Thus x decreases on each call after that (since x mod y < y , y is also strictly decreasing)

To complete the proof we show that x is halved every two calls, that is O(lgx) recursive calls to computer GCD.

If x >= 2y then x’ <= x /2   (halved in one step)

Else x<2y then y’ = x mod y = x - y < x - x/2 = x/2

Since y > x /2

Therefore step two swap positions thus x” < x / 2 (two steps)

Thus halved every two steps at most.

Definition: A language is in NP if it is decided by some NTM in polynomial time.
Example: HAMPATH = { <G,s,t> | where G is a diagraph with a hamilton path from s to t}

Theorem HAMPATH ∈ NP

Proof: The following NTM decides hamilton path.

mark[i] = 0    for all i ∈ V(G)
mark[s] 1; v = s

for n - 1 iterations do
{

non deterministic pick u ∈ V (G)
if mark[u] != 0 or (v,u) !∈ E(G)
v = u ; mark[v] = !

}

if v = T accept
else reject

Definition: A verifier for a language A is a deterministic algorithm V where L = { x | V accepts <x,w> for some string w}

1. w is called the witess of proof (certificate)
2. |w| of poly-length of x
3. The time of a verifier runs in is with respect to |x|