## 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