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

Q. A generalization of P class can be:

View solution

Q. Which of the following options are correct with reference to P-complete problems?

View solution

Q. A problem X belongs to P complexity class if there exist ________ algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input.

View solution

Q. Which of the following is a P-complete type of problem?

View solution

Q. State true or false?
Statement: Given a turing machine, an input for the machine, and a number T(unary), does that machine halt on that input within the first T-steps?

The given problem is P-complete.

View solution

Q. What does NP stands for in complexity classes theory?

View solution

Q. The hardest of NP problems can be:

View solution

Q. Which of the following contains NP?

View solution

Q. Travelling sales man problem belongs to which of the class?

View solution

Q. State true or false?
Statement: If a problem X is in NP and a polynomial time algorithm for X could also be used to solve problem Y in polynomial time, then Y is also in NP.

View solution