500 views
0 votes
0 votes

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?

  1. SP is NP-hard, LP is not
  2. LP is NP-hard, SP is not
  3. Both are NP-hard
  4. Neither SP nor LP is NP-hard

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
SPluto asked May 2, 2019
563 views
Let L1 and L2 be 2 languages which are not regular. Which of these is true?The union of L1 and L2 is not regular.The intersection of L1 and L2 is not regular.Both I and I...
1 votes
1 votes
1 answer
4