- Are the following problems NP-complete, NP-hard, P, or neither (you will need to research them on the internet)? - Subset-sum Shortest path in Graph - Longest path in Graph - Number of simple cycles in a graph - Feedback-Arc-Set - Sorting a list - Inserting in a Hash-table Bipartite Matching - Steiner Tree decision problem - Graph Isomorphism - Subgraph Isomorphism - 2-Graph Coloring - 3-Graph Coloring 2-SAT - 3-SAT SAT - MQ (multivariate quadratic equation solving) - Linear Programming - Integer Linear Programming (ILP) Can you reduce 3-graph coloring to SAT (i.e. solve coloring using SAT)? Please show how to do this reduction. To show that 3-graph coloring is NP-complete, do you have to reduce it to SAT, or do you have to reduce SAT to it? - Are the following problems NP-complete, NP-hard, P, or neither (you will need to research them on the internet)? - Subset-sum Shortest path in Graph - Longest path in Graph - Number of simple cycles in a graph - Feedback-Arc-Set - Sorting a list - Inserting in a Hash-table Bipartite Matching - Steiner Tree decision problem - Graph Isomorphism - Subgraph Isomorphism - 2-Graph Coloring - 3-Graph Coloring 2-SAT - 3-SAT SAT - MQ (multivariate quadratic equation solving) - Linear Programming - Integer Linear Programming (ILP) Can you reduce 3-graph coloring to SAT (i.e. solve coloring using SAT)? Please show how to do this reduction. To show that 3-graph coloring is NP-complete, do you have to reduce it to SAT, or do you have to reduce SAT to it