Understanding Complexity Classes

What is time complexity?

• Time complexity measures the time an algorithm takes to run as a function of the input size.

• Time complexity indicates the number of lines of code in an algorithm.

• Time complexity is the measure of memory usage of an algorithm.

• Time complexity refers to the physical time taken by a computer to execute a program.

Define asymptotic notation.

• Asymptotic notation is used to measure the accuracy of algorithms.

• Asymptotic notation includes Big O, Big Omega, and Big Theta notations, which characterize the growth rates of functions.

• Asymptotic notation only includes Big O notation.

• Asymptotic notation refers to the average case performance of algorithms.

What does P stand for in computational complexity?

• Polynomial space

• Pseudopolynomial time

• Prime time

• Polynomial time

Explain the NP problem.

• The NP problem is a class of problems solvable in linear time.

• The NP problem is a class of decision problems verifiable in polynomial time.

• The NP problem refers to non-deterministic polynomial time algorithms only.

• The NP problem is a type of optimization problem that cannot be verified.

What is the difference between P and NP problems?

• P problems can be solved in polynomial time; NP problems can be verified in polynomial time.

• P problems can be verified in linear time; NP problems can only be solved in exponential time.

• P problems can be solved in exponential time; NP problems cannot be verified in polynomial time.

• P problems are always harder than NP problems; NP problems are easier to solve than P problems.

Define NP-hard problems.

• NP-hard problems are problems for which every problem in NP can be reduced to them in polynomial time, and they may not be solvable in polynomial time.

• All NP-hard problems are also NP-complete.

• NP-hard problems can be solved in linear time.

• NP-hard problems are a subset of NP problems.

What are NP-complete problems?

• NP-complete problems are a subset of P problems.

• NP-complete problems are only solvable in polynomial time.

• NP-complete problems are decision problems that are both in NP and NP-hard.

• NP-complete problems can be solved in linear time.

Give an example of a P problem.

• Determining if a number is prime

• Calculating the factorial of a number

• Sorting a list of names alphabetically

• Finding the greatest common divisor of two numbers

How can you prove a problem is NP-complete?

• Show the problem is in P and reduce it to a known NP problem.

• Prove that the problem can be solved using a greedy algorithm.

• Demonstrate that the problem has a polynomial-time solution.

• Show the problem is in NP and reduce a known NP-complete problem to it.

What is polynomial time reduction?

• Polynomial time reduction is a technique to transform one problem into another in polynomial time to analyze their complexity.

• A technique to combine multiple problems into one.

• A method to solve problems in constant time.

• A way to classify problems as easy or hard.