Question

please answer and I will rate!

4. a) Define the concept of NP-completeness b) If A is NP-complete, and A has a polynomial time algorithm, then a polynomial time algorithm to find a longest path in a directed graph. Answer:

Answer 1

4a.

• Np complete is a problem which is used to solved by the brute force algorithm or polynomial time algorithm. Each problem’s input should added with a solution of length of polynomial and those problem’s tested very fast like If solution set is empty then output will be NO for input and If solution set is non-empty then output will be YES for input. The complexity of problem is called NP and if NP can be converted to polynomial time then it is called NP hard. The combination of both NP and NP hard is called Np complete. So Np complete present the problem and it has polynomial time algorithm to solve.

4b.

• Using a polynomial time algorithm to find the longest path in a directed graph, Basically in graph theory the longest path problem is use to find a simple path that is of the maximum length in the provided graph. A path is known simple if it does not have any vertices repeated; the path’s length can be measured by checking its no. of edges,and also by the sum of the weights of its edges. Unlike the case of shortest path problem, that is possible to be solved in polynomial time in graphs without any involvement of negative-weight cycles, where the longest path problem is considered to be NP-hard and also in decision version of this problem, is NP-complete. Which signifies that the decision problem is not possible to be solved in the given polynomial time for any of the current arbitrary graphs until it is P = NP. More Stronger results implies that it is not that simple for a prior approximation. Although, it is having a linear time solution for any directed graphs, that is having an important implementation in finding out the longest path for the relevant problems.

*Please give a thumbs up if you find this solution helpful.