P & NP Flashcards
1
Q
Class P
A
P = Union of TIME(n^k)
Class of decision problems that can be solved by a deterministic TM in polynomial time
2
Q
Class NP
A
NP = Union of NTIME(n^k)
Class of decision problems with polynomial time verifiers
3
Q
L can be decided by some nondeterministic TM in polytime iff ____________
A
L ∈ NP
4
Q
Clique Decision Problem
A
CLIQUE = {<G, k>: G is an undirected graph with a k-clique}, where a clique is a set of vertices that are all directly connected to each other
CLIQUE ∈ NP
5
Q
Path Decision Problem
A
PATH = {<G, s, t>: G is a directed graph with path from s to t}
PATH ∈ P
