Lecture 22 (Time Complexity), 11/27/17

Concepts, definitions (in italics):





Boolean Algorithm

Corresponding language

Given graph G and nodes s and e in G, does there exist a path from s to e in G?

PATH = {<G,s,e>: G is a graph, s and e are nodes in G, and there exists path(s,e) in G}

Given numbers x, y, are they relatively prime?

RELPRIME = {<x,y>: x and y are integers and there does not exist
k > 1 that is a divisor for both x and y}

Given k, is k composite (non-prime)?

COMPOSITE = {<k>: k is a natural that is composite (not prime)}


CLIQUE = {<G,k>: G is a graph which has a clique of size k}


HAMPATH = {<G>: G is a graph which has a Hamiltonian path}