Automata Problems

Eulerian Tour

Inputs: Graph G

Status: P

Asks to compute a closed walk that uses every edge exactly once. It has a clean structural characterization (G must be connected and every vertex must have an even degree), which translates directly to an efficient greedy algorithm running in polynomial time.

Hamiltonian Cycle

Inputs: Graph G

Status: NP
Asks to compute a cycle that visits every vertex exactly once. It has no known structural characterization and no known fast algorithm, but there is a fast algorithm that can easily verify a given solution.

2-COL

Inputs: Graph G

Status: P

Also known as testing if a graph is Bipartite. Asks to assign up to 2 colors to vertices such that adjacent vertices get different colors. Characterized by having no odd cycles and can be efficiently solved/tested in linear time using Breadth-First Search (BFS)

3-COL

Inputs: Graph G

Status: NP

Asks to assign up to 3 colors to vertices such that adjacent vertices get different colors. Unlike 2-Coloring, it has no clean structural characterization and no known efficient algorithm to find a coloring, although verifying a given coloring is easy.

PATH

Inputs: Graph G, Vertex s, Vertex t, Integer k

Status: P

Defined as the language PATH = {(G, s, t, k) : G has a path of length <= k from s to t}. It is the decision-problem equivalent of computing the shortest path from s to t.

Primality Testing

Inputs: Integer x
Status: P
Checks whether the input integer x is a prime number. While a naive O(x) algorithm is exponential relative to the input size O(log x), the AKS algorithm (Agrawal–Kayal–Saxena) runs in polynomial time.

Integer Factoring (FACT)

Inputs: Integer x, Integer k

Status: NP
Does a factor of x less than or equal to d exist?'

It belongs to both NP and coNP, meaning it is not expected to be NP-complete. It can be solved in polynomial time on a quantum computer using Shor's Algorithm but classical complexity is not known to be in P

3SAT

Input: 3CNF Formula $\phi$

Status: NP, NP-Complete

A restriction of the Satisfiability problem where the formula is in 3CNF form[cite: 931]. It is verifiable in polynomial time given a truth assignment [cite: 798, 799] and is classified as NP-complete

SAT

Inputs: Boolean formula $\phi$
Status: NP, NP-Complete

Stands for Satisfiability[cite: 3]. Proved to be NP-complete via the Cook-Levin Theorem, establishing that every problem in NP can be Karp-reduced to it

Bipartite Perfect Matching

Inputs: Bipartite Graph G = (L u R, E)

Status: P

If the bipartite graph contains a matching where every vertex is matched[cite: 1097]. Solvable in polynomial time, which generalizes to perfect matchings in any graph.

Three-Dimensional Matching (3DM)

Inputs: Set A, Set B, Set C, Set of triples E

Status: NP, NP-Complete

A natural generalization of Bipartite Perfect Matching into triples[cite: 1103]. Asks if there exist n pairwise disjoint triples that cover all elements of A U B U C[cite: 1102]. Proven to be NP-complete.

Zero-One Equations (ZOE)

Inputs: Matrix A (binary), Vector b (binary)
Status: NP, NP-Complete
Consists of m linear equations over n binary variables where coefficients and RHS values are in {0,1}[cite: 1107, 1108]. Asks if there is a binary solution assignment satisfying all equations[cite: 1109]. 3DM can be Karp-reduced to ZOE.

Independent Set (INDSET)

Inputs: Graph G, Integer k

Status: NP, NP-Complete

Whether an independent set of size k exists[cite: 3]. It is shown that the decision, search, and optimization versions of Independent Set are all Cook-reducible to each other, making them polynomially equivalent[cite: 26, 27]. While it is NP-hard in general [cite: 34], exploiting special structures (like dynamic programming over structured graphs) can result in polynomial-time algorithms

Minimum Vertex Cover

Inputs: Undirected Graph G = (V, E)
Status: NP-Hard

An optimization problem seeking a subset of vertices C of smallest possible size such that every edge has at least one endpoint in C[cite: 302]. The decision version is NP-hard[cite: 276, 538]. Since exactly solving it is not possible in polynomial time (assuming P != NP) [cite: 494], a polynomial-time 2-approximation algorithm called GreedyVC can be used, which guarantees finding a valid vertex cover within twice the size of the optimal solution.

Minimum Set Cover

Inputs: Universe U = {1,2,…,n}, Collection S = {S1, … Sm} of subsets of U
Status: NP, NP-Complete

The optimization task is to find a smallest subset of collections whose union covers the universe[cite: 377]. The decision version ('Is there a set cover of size at most k?') is proven to be NP-complete via a reduction from the vertex cover problem

Knapsack

Input: n items with values v and weights w, Capacity ‘C’ or ‘W’
Status: NP-Hard

The optimization goal is to maximize total value without exceeding the weight capacity W. While exactly solving it in general is NP-hard, it admits a Polynomial Time Approximation Scheme (PTAS). Specifically, the DynamicAppKs algorithm uses a scaling parameter θ to achieve an approximation factor of 1 - ε in O(n^3 / ε) time, allowing an arbitrarily accurate solution in polynomial time for any fixed ε

Maximum Clique

Inputs: Graph G
Status: NP-Hard
Listed as an NP-hard optimization problem for which no efficient polynomial-time solution is believed to exist

Maximum Cut

Inputs: Graph G
Status: NP-Hard

Listed as an NP-hard optimization problem for which no efficient polynomial-time solution is believed to exist

Minimum Dominating Set

Inputs: Graph G
Status: NP-Hard
Listed as an NP-hard optimization problem for which no efficient polynomial-time solution is believed to exist

General Travelling Salesperson Problem (General TSP)

Inputs: Complete weighted undirected Graph G = (V, E, w) with non-negative edge weights w(e)
Status: NP-Hard
The objective is to find a cycle that visits each vertex exactly once and minimizes total weight. General TSP is strictly inapproximable within any factor unless P = NP.

Metric Travelling Salesperson Problem (Metric TSP)

Inputs: Complete weighted undirected Graph G = (V, E, w) satisfying the triangle inequality
Status: NP-Hard

A structured variant of TSP where edge weights obey the triangle inequality (w(u,v) <= w(u,x) + w(x,v)). Thanks to this structural property, it is approximable. The 'FindTour' algorithm constructs a Minimum Spanning Tree (MST), doubles its edges to find an Eulerian tour, and shortcuts repeated vertices to yield a valid TSP tour that acts as a 2-approximation algorithm running in polynomial time.

ILP

Inputs: Linear constraints with integer constraints, Objective function
Status: NP-Hard
An optimization problem where variables must take integer values. It is classified as an NP-hard optimization problem. It is contrasted with standard Linear Programming (LP), which drops the integer requirement and can be solved in polynomial time.

MAXINDSET

Inputs: Graph G
Status: NP-Hard, NP-Complete
Given Graph G, find an independent set that contains the maximum possible number of vertices