18 Questions
A decision problem can be both in P and NP sets.
True
NPC is a subset of NP-hard problems.
False
A problem can be proven to be NPC by reducing it to a known NPC problem.
False
A Hamiltonian cycle is a cycle that visits each vertex at least twice.
False
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.
False
3-coloring a planar map is a problem that can be solved in polynomial time.
False
NP stands for 'not polynomial'.
False
A polynomial-time decision algorithm is used to verify solutions in NP problems.
False
P is a subset of NP (P ⊆ NP).
True
The question of whether P = NP is still an open problem.
True
A nondeterministic Turing machine can explore many paths of computation in parallel.
True
A polynomial-time decision algorithm can be used to decide whether a given integer is composite.
True
All the algorithms studied in CIS 606 have a worst-case running time of O(nk), where k is a constant.
True
A decision problem always has a feasible solution with the best (minimum or maximum) value.
False
A polynomial time algorithm can solve all problems.
False
The Knapsack problem is an example of a decision problem.
False
Dynamic programming is a technique used to solve decision problems.
False
Determining whether a number is prime is a decision problem.
True
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
Test your knowledge of graph theory concepts, including graph coloring and vertex cover problems. Solve exercises and quizzes to improve your understanding of these fundamental computer science topics.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
