Exam 3 - NP Reductions Definitions Flashcards
1
Q
Polynomial runtime
A
O(n^k) for some constant k
2
Q
Exponential runtime
A
O(k^n) for some k > 1
3
Q
Pseudopolynomial runtime
A
Polynomial to the magnitude of the input, but exponential to the size of the input
4
Q
NP complexity class
A
Nondeterministic polynomial class of all search/decision problems
5
Q
NP problems have solutions that can be verified in ____ time
A
polynomial
6
Q
P complexity class
A
Class of search problems that are solvable in polynomial time
7
Q
NP-completeness
A
NP problem that other NP-complete problems can be reduced to in polynomial time
8
Q
NP-Hard
A
problems that are at least as hard as NP class problems
9
Q
Are NP-hard problems in class NP?
A
not necessarily
10
Q
True/False : P is at least a subset of NP
A
True
11
Q
Do we know if knapsack is in NP?
A
No, but we also don’t know that it isn’t
