To login with Google, please enable popups

or

Don’t have an account? Sign up

To signup with Google, please enable popups

or

Sign up with Google or Facebook

or

By signing up I agree to StudyBlue's

Terms of Use and Privacy Policy

Already have an account? Log in

Reminder

Edit a Copy

Study these flashcards

- District-of-columbia
- George Washington University
- Computer Science
- Computer Science 3212
- Pless
- Np Problems

Anonymous

• 10

cards
Vertex Cover

Set of vertices of graph G where each edge b belonging to V is incident to at least one vertex of the set

Independent Set

set of vertices in a graph where none are adjacent (Let S be the independent set, for every edge in S, there is no edge to any any other edge in S)

Clique

set of vertices in a graph where every two vertices in the clique are adjacent (fully connected, from any vertex in the clique, it is connected to all other vertices in the clique)

SAT, 3-SAT

Given a boolean function, determine the truth values required for all variables to make it true (3-sat is same thing except each clause has 3 variables)

Colorability

checking if graph is k-colorable (because you have to check every node)

Knapsack

Given a set of items, each with weight and value, determine the number of each item to include in a collection so that the total weight is as close to a limit as possible without going over

Subset Sum

P

NP

NP-complete

Sign up for free and study better.

Anytime, anywhere.

Get started today!

Find materials for your class:

Download our app to study better. Anytime, anywhere.