Podcast
Questions and Answers
A decision problem can be both in P and NP sets.
A decision problem can be both in P and NP sets.
True (A)
NPC is a subset of NP-hard problems.
NPC is a subset of NP-hard problems.
False (B)
A problem can be proven to be NPC by reducing it to a known NPC problem.
A problem can be proven to be NPC by reducing it to a known NPC problem.
False (B)
A Hamiltonian cycle is a cycle that visits each vertex at least twice.
A Hamiltonian cycle is a cycle that visits each vertex at least twice.
A vertex cover of a graph is a set of edges such that each vertex is incident to at least one edge of this set.
A vertex cover of a graph is a set of edges such that each vertex is incident to at least one edge of this set.
3-coloring a planar map is a problem that can be solved in polynomial time.
3-coloring a planar map is a problem that can be solved in polynomial time.
NP stands for 'not polynomial'.
NP stands for 'not polynomial'.
A polynomial-time decision algorithm is used to verify solutions in NP problems.
A polynomial-time decision algorithm is used to verify solutions in NP problems.
P is a subset of NP (P ⊆ NP).
P is a subset of NP (P ⊆ NP).
The question of whether P = NP is still an open problem.
The question of whether P = NP is still an open problem.
A nondeterministic Turing machine can explore many paths of computation in parallel.
A nondeterministic Turing machine can explore many paths of computation in parallel.
A polynomial-time decision algorithm can be used to decide whether a given integer is composite.
A polynomial-time decision algorithm can be used to decide whether a given integer is composite.
All the algorithms studied in CIS 606 have a worst-case running time of O(nk), where k is a constant.
All the algorithms studied in CIS 606 have a worst-case running time of O(nk), where k is a constant.
A decision problem always has a feasible solution with the best (minimum or maximum) value.
A decision problem always has a feasible solution with the best (minimum or maximum) value.
A polynomial time algorithm can solve all problems.
A polynomial time algorithm can solve all problems.
The Knapsack problem is an example of a decision problem.
The Knapsack problem is an example of a decision problem.
Dynamic programming is a technique used to solve decision problems.
Dynamic programming is a technique used to solve decision problems.
Determining whether a number is prime is a decision problem.
Determining whether a number is prime is a decision problem.
Flashcards are hidden until you start studying
Study Notes
Graph Problems
- 3-COLOR problem: Given a planar map, can it be colored using 3 colors so that no adjacent regions have the same color?
- VERTEX COVER problem: Given a graph G(V,E) and a positive integer k, find a vertex cover of size at most k
- HAMILTONIAN CYCLE problem: Given an undirected graph, is there a Hamiltonian cycle in this graph?
NP-Completeness
- NPC problem: A problem B is NPC if B is in NP and every problem in NP can be reduced to B in polynomial time
- To prove that a problem B is NPC: B is in NP, and there is a polynomial transformation from a known NPC problem A to B
P and NP
- P: a set of decision problems that can be solved in polynomial time
- NP: a set of decision problems that can be verified in polynomial time
- NP is a subset of NP and as hard as other problems in NP
- NP-Hard: the set of problems that every NP problem can be reduced to one of it
Decision Problems
- Decision Problem: a problem of determining an answer to a class of yes/no questions
- Examples: given a graph G, vertices u and v, an integer k, does a path exist from u to v consisting of at most k edges?; does a graph have a path that goes through every node exactly once?; is the number x prime?
- A solution to a decision problem is given by an algorithm that answers yes or no
Optimization Problems
- Optimization Problem: the answer of the problem is a feasible solution with the best (minimum or maximum) value
- Examples: knapsack problem, single-source shortest path, maximum flow, dynamic programming, divide-and-conquer, prune-and-search
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
