a. Briefly define each of the following: i. Decision problem i. Nondeterministic machine ii. NP iv. NP-complete problem b. What is the satisfiability decision problem (SAT)? c. State the Cook-Levin Theorem.
a
i. Decision problem:
It is a type of problem where it can be given as a yes or no as the input values that is in a computational complexity theory and in a computability theory. For example let us consider the prime number where it is to be checked whether it is prime or not and by using this decision tree we will be able to know it easily and this is mainly solved with an algorithm which is known as decidable.
ii. Non deterministic machine:
If the governing steps will specialize more than one action which is possible in a particular situation then that is called as a non deterministic machine, that means the performance of the later state will be depending on the present symbol of which it sees.
iii. NP:
NP stands for Non deterministic polynomial time. It is mainly used to define the decision problem, it is a collection of decision problems that the instances of the problem occur.
iv. NP complete problem:
If a given solution that can be guessed and if it can be answered then that particular problem is called as NP complete problem and that must be in a given polynomial time and when coming to non deterministic then that cannot be answered in a given amount of time, now if a particular problem is NP and the remaining all are the NP problem which are reducible at a given time then that problem is termed as NP complete problem.
Step by step
Solved in 2 steps
