#2
 
 
Re: IGNOU MCA Previous Year Question Papers
As per your requirement here I am uploading a document file having the IGNOU MCA Previous Year Question Papers. This attachment contains descriptive types of the questions. The answers are also available in it. I have taken following questions from the attachment: 5.(a) Define N Pcomplete & problems. Ans. NP Complete Problem: A problem P or equivalently its language L1 is said to be NP complete if the following two conditions are satisfied: a) The problem L2 is in the class NP. b) For any problem L2 in NP, there is a polynomial time reduction of L1 to L2. NP Hard Problem: A problem L is said ti be NP – Hard if for any problem L1 in NP, there is a polynomial time reduction of L1 to L. In other words, a problem L is hard if only condition (b) of NP – completeness is satisfied. We can conclude form the definitions that every NP – complete problem L must be NP  Hard & additionally should satisfy the condition that L is an NP – class problem. In general, the process of establishing a problem as NP – complete is a two step process. a) The first step, which in most of the cases is quite simple, constitutes of guessing possible solutions of the instances, one instance at a time, of the problem & then guess actually is a solution or not. b) The second step involves designing a polynomial time algorithm which reduces instances of an already known NP  complete problem to instances of the problem, which is intended to be shown as NP – complete. Remaining questions are in the attachment please click on it…
__________________ Answered By StudyChaCha Member 
Sponsored Links 
Have a Facebook Account? Ask your Question Here 
