NP reference Flashcards
SAT Definition
Determine if a boolean formula in CNF can be satisfied by assigning true/false values to its variables.
- A CNF formula is an AND of clauses, each an OR of literals.
SAT Input
Boolean formula with n variables and m clauses.
SAT Output
A satisfying assignment for each variable (or NO if none exists).
Verification: Check each clause to ensure at least one literal evaluates to true under the given assignment.
Runtime: O(nm) - must check all m clauses, each with up to n literals.
3SAT Definition
Case of SAT where each clause has at most 3 literals.
3SAT Input
Boolean formula, each clause with at most 3 literals.
3SAT Output
A satisfying assignment for each variable (or NO if none exists).
Verification: Check each clause to ensure at least one literal evaluates to true.
Runtime: O(m) - checking each clause takes constant time (maximum 3 literals per clause).
Clique Definition
Determine if a graph has a clique of size k.
- A subset of vertices where every pair is connected by an edge.
Clique Input
Undirected G = (V, E); integer k.
Clique Output
A set of k vertices forming a clique (or NO if none exists).
Verification: Check that every pair of vertices in the solution set has an edge between them.
Runtime: O(n²) - need to check all pairs of vertices in the solution.
Independent Set Definition
Determine if a graph has an independent set of size k.
- A subset of k vertices with no edge between them.
Independent Set Input
Undirected G = (V, E); integer k.
Independent Set Output
A set of k vertices forming an independent set (or NO if none exists).
Verification: Check that no pair of vertices in the solution set has an edge between them.
Runtime: O(n²) - need to check all pairs of vertices in the solution.
Vertex Cover Definition
Determine if a graph has a vertex cover of size at most k.
- A subset of vertices such that every edge in E has at least one endpoint in the subset.
Vertex Cover Input
Undirected G = (V, E); integer k.
Vertex Cover Output
A set of ≤ k vertices forming a vertex cover (or NO if none exists).
Verification: Check that every edge in the graph has at least one endpoint in the solution set.
Runtime: O(m) - need to check each edge in the graph.
Rudrata Path Definition
Determine if a graph has a path from vertex s to vertex t that visits each vertex exactly once.
Rudrata Path Input
Graph G = (V, E); Two vertices in V: s and t.
Rudrata Path Output
A path from s to t visiting every vertex exactly once (or NO if none exists).
Verification: Check that the path starts at s, ends at t, visits all vertices, and each pair of consecutive vertices in the path has an edge between them.
Runtime: O(n) - need to check each vertex appears exactly once and consecutive vertices are connected.
Rudrata Cycle Definition
Determine if a graph has a cycle that visits each vertex exactly one time.
Rudrata Cycle Input
Graph G = (V, E).
Rudrata Cycle Output
A cycle visiting every vertex exactly once (or NO if none exists).
Verification: Check that the sequence forms a valid cycle (last vertex connects to first), contains all vertices exactly once, and each pair of consecutive vertices has an edge between them.
Runtime: O(n) - need to check each vertex appears exactly once and consecutive vertices are connected.
TSP Definition
Determine if a complete weighted graph has a tour visiting all vertices with total weight at most a bound.
TSP Input
Complete graph G = (V, E); edge weights w(i, j); Bound B.
TSP Output
A tour with total weight ≤ B (or NO if none exists).
Verification: Check that the tour visits all vertices exactly once, returns to the starting vertex, and has total weight ≤ B.
Runtime: O(n) - need to check each vertex appears exactly once and calculate the total weight.
Subset Sum Definition
Determine if there exists a subset of a given set of integers that sums exactly to a target value.
Subset Sum Input
A set of integers S = {a₁, a₂, …, aₙ}; A target integer t.
Subset Sum Output
A subset of S summing to t (or NO if none exists).
Verification: Sum the integers in the proposed subset and check if the sum equals t.
Runtime: O(n log t) - need to sum at most n integers, each requiring O(log t) space.
ILP Definition
Determine if there exists an integer solution to a system of linear constraints that achieves a target objective value.
ILP Input
Objective function C^T x, constraints Ax ≤ b, x integer; Target value k.
ILP Output
An integer vector x satisfying the constraints and achieving objective value ≥ k (or NO if none exists).
Verification: Check that x contains integers, Ax ≤ b is satisfied, and C^T x ≥ k.
Runtime: O(mn) where A is an m×n matrix - need to verify all constraints.
ZOE Definition
Determine if there exists a 0-1 assignment to variables that satisfies a system of linear equations where each equation sums to 1.
ZOE Input
System Ax = 1, where A is an m×n 0-1 matrix, x is a 0-1 vector.
ZOE Output
A 0-1 vector x satisfying Ax = 1 (or NO if none exists).
Verification: Check that x contains only 0s and 1s, and Ax = 1.
Runtime: O(mn) - need to multiply the m×n matrix A by the n-vector x.
3D Matching Definition
Determine if a set of triples can be selected to cover three sets exactly once.
3D Matching Input
Three disjoint sets X, Y, Z, each of size n; A set of triples T ⊆ X×Y×Z.
3D Matching Output
A subset of n disjoint triples covering X∪Y∪Z (or NO if none exists).
Verification: Check that the solution contains exactly n triples, each element of X, Y, and Z appears in exactly one triple.
Runtime: O(n) - need to verify each element appears in exactly one triple.
k-Colorings Definition
Determine if each adjacent vertices get different colors
k-Colorings Input
undirected G=(V,E) & integer k > 0
k-Colorings Output
Assignments of color for each v in V
Verification: Check that for all (x,y) in E that color(x) != color(y)
Runtime: O(n+m) to walk the adjacency list to verify
if a NP-Complete problem can be solved in poly-time, then…
All problems in NP can be solved in poly-time.
[3SAT]
When reducing SAT -> 3SAT, each new k-3 variables are unique for each clause
True
[SAT to 3SAT]
Runtime to create additional clauses during input transform
O(mn)
There are m clauses with at most n literals
[3SAT]
Runtime to return the output
O(mn)
There are at most O(m(n-3)) new variables, so removing them takes at most O(m(n-3)+n) (ie. new vars + old vars) which simplify to O(mn)
Examples of P problems
2SAT, Horn SAT
MST
Shortest Path
Bipartite matching
Unary Knapsack
IS on trees
LP
Euler path
Minimum cut
Diff between Euler vs Rudrata Path
Euler - path that uses every edge of a graph exactly once
Rudrata - visits every vertex of a graph exactly once
[Hitting Set]
Input Transformation runtime
O(n^2 m)
