# 14 NP problems in A. Lucas (2014)

Fixstars Amplify is used to solve the 14 NP problems presented in the paper, A. Lucas, Front. Phys. (2014).   Tutorials (applied)

#### 1. Graph Partitioning Problem

Difficulty level     In this tutorial, we will partition a graph into two sets with the same number of vertices so that we minimize the number of edges connecting two points belonging to different sets. Tutorials (applied)

#### 2. Maximum Clique Problem

Difficulty level     For a given graph, we find the subset of vertices that has the most significant number of vertices where an edge connects any two vertices in the subset. Tutorials (applied)

#### 3. Exact Cover Problem

Difficulty level     Suppose we have a set and are given several subsets of that set. In the exact cover problem, we choose subsets so that precisely one of the selected subsets contains any element of the set. Tutorials (applied)

#### 4. Set Packing Problem

Difficulty level     Suppose we have a set and are given several subsets of the set. In the set packing problem, we choose the subsets that have no common part so that the number of elements in the chosen subset is maximized. Tutorials (applied)

#### 5. Minimum Vertex Cover Problem

Difficulty level     A vertex cover is a subset of the vertices of a graph such that every edge of the graph is connected to a vertex of this subset. The minimum vertex cover problem finds the vertex cover with the fewest elements. Tutorials (applied)

#### 6. Satisfiability Problem (SAT)

Difficulty level     Given a single Boolean formula, it may be possible to make the value of the formula true by successfully determining the values of the variables in it. The satisfiability problem determines this, and we will solve a problem called 3-SAT. Tutorials (applied)

#### 7. Minimum Maximum Matching Problem

Difficulty level     In this tutorial, we will find a subset of the edges of a given graph where the edges in the subset are not adjacent to each other, and the edges not in the subset are always adjacent to the edges in the subset, with the fewest elements. Tutorials (applied)

#### 8. Graph Coloring Problem

Difficulty level     The graph coloring problem involves coloring the vertices of a graph with a given number of colors and determining whether or not the vertices connected by edges can be colored with different colors. Tutorials (applied)

#### 9. Clique Cover Problem

Difficulty level     Given a graph and a certain number of colors, the clique cover problem is the problem of determining whether it is possible to paint the vertices of the graph so that edges connect all pairs of vertices of the same color. Tutorials (applied)

#### 10. Job Sequencing Problem

Difficulty level     Suppose you have several jobs and machines, and you know how long each job will take. You assign each job to one of the machines. The job scheduling problem asks how to assign the jobs to complete all jobs as quickly as possible. Tutorials (applied)

#### 11. Hamiltonian Cycle Problem

Difficulty level     For a given graph, a closed path that passes through all graph vertices once and returns to its origin is called a Hamiltonian cycle, and in general, for large graphs, it is difficult to determine whether such a path exists. Tutorials (applied)

#### 12. Directed Feedback Vertex Set Problem

Difficulty level     Given a directed graph, a directed feedback vertex set is a subset of graph vertices such that the closed path of any graph passes through at least one vertex in the subset. The directed feedback vertex set problem seeks to find a set with the fewest elements. Tutorials (applied)

#### 13. Minimum Feedback Edge Set Problem

Difficulty level     Given a directed graph, a feedback edge set is a subset of graph edges where every closed path contains at least one edge in this subset. The minimum feedback edge set problem searches for a feedback edge set with the fewest elements. Tutorials (applied)

#### 14. Graph Isomorphism Problem

Difficulty level     Two given graphs are said to be isomorphic if there is a one-to-one correspondence between their vertices and if the two corresponding vertices are both connected by an edge. It is generally challenging to determine isomorphism, but this example program tackles this problem.