NP reference

Question 1

SAT Definition

Answer 1

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.

Question 2

SAT Input

Answer 2

Boolean formula with n variables and m clauses.

Question 3

SAT Output

Answer 3

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.

Question 4

3SAT Definition

Answer 4

Case of SAT where each clause has at most 3 literals.

Question 5

3SAT Input

Answer 5

Boolean formula, each clause with at most 3 literals.

Question 6

3SAT Output

Answer 6

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).

Question 7

Clique Definition

Answer 7

Determine if a graph has a clique of size k.

• A subset of vertices where every pair is connected by an edge.

Question 8

Clique Input

Answer 8

Undirected G = (V, E); integer k.

Question 9

Clique Output

Answer 9

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.

Question 10

Independent Set Definition

Answer 10

Determine if a graph has an independent set of size k.

• A subset of k vertices with no edge between them.

Question 11

Independent Set Input

Answer 11

Undirected G = (V, E); integer k.

Question 12

Independent Set Output

Answer 12

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.

Question 13

Vertex Cover Definition

Answer 13

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.

Question 14

Vertex Cover Input

Answer 14

Undirected G = (V, E); integer k.

Question 15

Vertex Cover Output

Answer 15

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.

Question 16

Rudrata Path Definition

Answer 16

Determine if a graph has a path from vertex s to vertex t that visits each vertex exactly once.

Question 17

Rudrata Path Input

Answer 17

Graph G = (V, E); Two vertices in V: s and t.

Question 18

Rudrata Path Output

Answer 18

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.

Question 19

Rudrata Cycle Definition

Answer 19

Determine if a graph has a cycle that visits each vertex exactly one time.

Question 20

Rudrata Cycle Input

Answer 20

Graph G = (V, E).

Question 21

Rudrata Cycle Output

Answer 21

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.

Question 22

TSP Definition

Answer 22

Determine if a complete weighted graph has a tour visiting all vertices with total weight at most a bound.

Question 23

TSP Input

Answer 23

Complete graph G = (V, E); edge weights w(i, j); Bound B.

Question 24

TSP Output

Answer 24

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.

Question 25

Subset Sum Definition

Answer 25

Determine if there exists a subset of a given set of integers that sums exactly to a target value.

Question 26

Subset Sum Input

Answer 26

A set of integers S = {a₁, a₂, ..., aₙ}; A target integer t.

Question 27

Subset Sum Output

Answer 27

A subset of S summing to t (or NO if none exists). ## Footnote 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.

Question 28

ILP Definition

Answer 28

Determine if there exists an integer solution to a system of linear constraints that achieves a target objective value.

Question 29

ILP Input

Answer 29

Objective function C^T x, constraints Ax ≤ b, x integer; Target value k.

Question 30

ILP Output

Answer 30

An integer vector x satisfying the constraints and achieving objective value ≥ k (or NO if none exists). ## Footnote 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.

Question 31

ZOE Definition

Answer 31

Determine if there exists a 0-1 assignment to variables that satisfies a system of linear equations where each equation sums to 1.

Question 32

ZOE Input

Answer 32

System Ax = 1, where A is an m×n 0-1 matrix, x is a 0-1 vector.

Question 33

ZOE Output

Answer 33

A 0-1 vector x satisfying Ax = 1 (or NO if none exists). ## Footnote 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.

Question 34

3D Matching Definition

Answer 34

Determine if a set of triples can be selected to cover three sets exactly once.

Question 35

3D Matching Input

Answer 35

Three disjoint sets X, Y, Z, each of size n; A set of triples T ⊆ X×Y×Z.

Question 36

3D Matching Output

Answer 36

A subset of n disjoint triples covering X∪Y∪Z (or NO if none exists). ## Footnote 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.

Question 37

k-Colorings Definition

Answer 37

Determine if each adjacent vertices get different colors

Question 38

k-Colorings Input

Answer 38

undirected G=(V,E) & integer k > 0

Question 39

k-Colorings Output

Answer 39

Assignments of color for each v in V ## Footnote 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

Question 40

if a NP-Complete problem can be solved in poly-time, then...

Answer 40

All problems in NP can be solved in poly-time.

Question 41

[3SAT] When reducing SAT -> 3SAT, each new k-3 variables are unique for each clause

Answer 41

True

Question 42

[SAT to 3SAT] Runtime to create additional clauses during input transform

Answer 42

O(mn) There are m clauses with at most n literals

Question 43

[3SAT] Runtime to return the output

Answer 43

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)

Question 44

Examples of P problems

Answer 44

2SAT, Horn SAT MST Shortest Path Bipartite matching Unary Knapsack IS on trees LP Euler path Minimum cut

Question 45

Diff between Euler vs Rudrata Path

Answer 45

Euler - path that uses every edge of a graph exactly once Rudrata - visits every vertex of a graph exactly once

Question 46

[Hitting Set] Input Transformation runtime

Answer 46

O(n^2 m)