Podcast
Questions and Answers
Which complexity class is defined as the class of problems that can be solved by an algorithm that runs in polynomial time on a deterministic computing machine?
Which complexity class is defined as the class of problems that can be solved by an algorithm that runs in polynomial time on a deterministic computing machine?
- NP-hard
- NP
- P (correct)
- NP-complete
Which complexity class is defined as the class of all problems that cannot be solved in polynomial time by any deterministic machine, although a candidate solution can be verified to be correct by a polynomial-time algorithm?
Which complexity class is defined as the class of all problems that cannot be solved in polynomial time by any deterministic machine, although a candidate solution can be verified to be correct by a polynomial-time algorithm?
- NP-complete
- NP (correct)
- P
- NP-hard
What is a problem called if it belongs to the class NP and all other problems in NP are polynomial transformable to it?
What is a problem called if it belongs to the class NP and all other problems in NP are polynomial transformable to it?
- NP
- P
- NP-complete (correct)
- NP-hard
What is a problem called if all problems in NP are polynomial transformable to it, but it has not been shown that the specific problem belongs to the class NP?
What is a problem called if all problems in NP are polynomial transformable to it, but it has not been shown that the specific problem belongs to the class NP?
Which complexity class is defined as the class of problems that can be solved by an algorithm that runs in exponential time on a deterministic computing machine?
Which complexity class is defined as the class of problems that can be solved by an algorithm that runs in exponential time on a deterministic computing machine?
