NP-Complete Problems Flashcards
Hamiltonian Path
Given: * a Graph * Nodes: s, t Find: Is there a path from s to t that passes through every node exactly once?
Travelling Salesman
Given: * a Graph, with Integer edge-weights * starting Node: s * integer budget: b Find: Is there a cycle from s back to s such that the total weight of the edges is less than b?
SAT (Satisfiability Problem)
Given:
* a conjunction (connected by ANDs) of Clauses, each Clause has boolean Literals connected by ORs
Ex: (a OR b OR c) AND (ā OR d OR b) AND…
Find:
Is there a combination of truth-values for the literals that can make the statement true?
Ex: make a=True, b=False, etc.
Aka, have at least one literal in Every clause be true.
3SAT
Given:
* a conjunction (connected by ANDs) of Clauses, each Clause has maximum 3 boolean Literals connected by ORs
Ex: (a OR b OR c) AND (ā OR b) AND…
Find:
Is there a combination of truth-values for the literals that can make the statement true?
Ex: make a=True, b=False, etc.
Aka, have at least one literal in Every clause be true.
Longest Path
Given: * a Graph * Nodes: s, t *integer b Find: Is there a path from s to t that is at least length b or more?
Knapsack
Given:
* a set of Objects with Weights and Values
* a knapsack with fixed max capacity
Find:
Which set of objects can we fit into the knapsack to maximize total value? (CanNot divide objects into fractional pieces)
MaxClique
Given: * a Graph * integer k Find: Is there a clique (a set of nodes S such that every node in S is directly connected to every other node in S) of size at least k?
Independent Set
Given: * a Graph * integer k Find: Is there a set of nodes S such that no two nodes in S are directly connected, such that S is of size at least k?
Hamiltonian Cycle
Given:
* a Graph
Find:
Is there a cycle that passes through every node exactly once?
Reduce 3SAT to Independent Set
- For each clause, create a set of nodes corresponding to the literals in that clause. Connect all the nodes in the same set
- Across clauses, connect each node to all of its negations
Submit this graph, and k = # of clauses, to the Independent Set algorithm.
The set IS returns to are the nodes that should be set to True.
What is a Search Problem?
Finding a Good Enough solution that satisfies some requirement.
Ex: “… greater than b // … at most b”
What is an Optimization Problem?
Finding the Best / Optimal solution
Ex: the minimum, the maximum
What is P?
Set of all problems that can be solved in polynomial time
(Search & optimization problems)
P is inside NP. So if something is P, it’s also NP
What is NP
Non-deterministic Polynomial Time
Set of all SEARCH Problems with solutions that can be Verified in polynomial time
