Let SP be the problem of finding the shortest path between 2 nodes, and LP be the problem of finding the longest path between 2 nodes, in an unweighted, undirected graph. Which of the following is true?
- SP is NP-hard, LP is not
- LP is NP-hard, SP is not
- Both are NP-hard
- Neither SP nor LP is NP-hard