Question:
The Travelling Salesman’s is an example of which of the following class of problems?
The Travelling Salesman’s is an example of which of the following class of problems?
Show Hint
The Travelling Salesman Problem is NP-hard and does not have a polynomial-time solution unless P = NP.
Updated On: May 3, 2025
- NP-hard
- P
- C
- NP but not NP-hard
Hide Solution
Verified By Collegedunia
The Correct Option is A
Solution and Explanation
The Travelling Salesman Problem (TSP) is a classic problem in combinatorial optimization. It is known to be NP-hard, meaning that no polynomial-time algorithm is known to solve it efficiently, and it is at least as hard as the hardest problems in NP.
Thus, the correct answer is \( \text{NP-hard} \).
Thus, the correct answer is \( \text{NP-hard} \).
Was this answer helpful?
0
0
Top Questions on Computer Languages and Algorithms
- Order the following complexities in the increasing order: $ O(n^2), O(n^3), O(\log n), O(n \log n) $
- AP PGECET - 2024
- Computer Science & Information Technology
- Computer Languages and Algorithms
- Which of the following is an example of divide and conquer strategy?
- AP PGECET - 2024
- Computer Science & Information Technology
- Computer Languages and Algorithms
- Which of the following problems is an example of backtracking strategy?
- AP PGECET - 2024
- Computer Science & Information Technology
- Computer Languages and Algorithms
- Which of the following is not an algorithmic strategy?
- AP PGECET - 2024
- Computer Science & Information Technology
- Computer Languages and Algorithms
- The average case time complexity of quick sort is
- AP PGECET - 2024
- Computer Science & Information Technology
- Computer Languages and Algorithms
View More Questions
Questions Asked in AP PGECET exam
The rank of matrix \(\begin{bmatrix} k & -1 & 0 \\[0.3em] 0 & k & -1 \\[0.3em] -1 & 0 & k \end{bmatrix}\) is 2, for \( k = \)
- AP PGECET - 2024
- Rank of a Matrix
If \(A = \begin{bmatrix} 4 & 2 \\[0.3em] -3 & 3 \end{bmatrix}\), then \(A^{-1} =\)
- AP PGECET - 2024
- Inverse of a Matrix
A two-port network is defined by the relation
\(\text{I}_1 = 5V_1 + 3V_2 \)
\(\text{I}_2 = 2V_1 - 7V_2 \)
The value of \( Z_{12} \) is:- AP PGECET - 2024
- Two Port Networks
An induction motor when started on load does not accelerate up to full speed but runs at \({\frac {1}{17}}\)th of the rated speed. The motor is said to be:
- AP PGECET - 2024
- Induction Motor
A 0 to 30 V voltmeter has an error of \(\pm 2\%\) of FSD. What is the range of readings if the voltage is 30V?
- AP PGECET - 2024
- Errors in Measurement
View More Questions