1.

Computational complexity of derangements is of __________(a) NP-complete(b) NP-hard(c) NP(d) PThe question was posed to me in unit test.The above asked question is from Counting topic in section Counting of Discrete Mathematics

Answer»

The correct ANSWER is (a) NP-complete

For EXPLANATION: Computational COMPLEXITY of derangements isNP-complete in order to determine whether a given permutation GROUP consists of any derangements or not.



Discussion

No Comment Found

Related InterviewSolutions