Q. An algorithm is called efficient if it runs in ____________ time on a serial computer.

View solution

Q. A problem is called __________ if its has an efficient algorithm for itself.

View solution

Q. A formal language is recursive if :

View solution

Q. Recursive languages are also known as:

View solution

Q. The class of recursive language is known as:

View solution

Q. Which of the following was not a part of Chomsky hierarchy ?

View solution

Q. According to the rice’s theorem, If P is a non trivial property, Lp is :

View solution

Q. Fill in the blank with reference to Rice’s theorem.
For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property.

View solution

Q. Which of the following is incorrect according to rice theorem?
Let S be a set of language hat is non trivial:

View solution

Q. Which of the following set of computable functions are decidable?

View solution

Q. Which of the following statements are undecidable?
For a given Turing Machine M,

View solution

Q. Post Correspondence problem is

View solution

Q. State true or false:
Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.

View solution

Q. PCP stands for?

View solution

Q. Can a Modified PCP problem be reduced to PCP?

View solution

Q. Consider three decision problem A, B, C. A is decidable and B is not. Which of the following is a correct option?

View solution

Q. If the number of steps required to solve a problem is O(n^k), then the problem is said to be solved in:

View solution

Q. The value of constants like p and e can be calculated in:

View solution

Q. Which of the following cannot be solved using polynomial time?

View solution

Q. The complexity class P consist of all the decision problems that can be solved by ___________using polynomial amount of computation time.

View solution