Lecture 22 (Time Complexity), 11/27/17
Concepts, definitions (in italics):
Reading:
Skills:
Notes:
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 |
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} |