Flashcards on Complexity Theory

Click on the flashcard to see the answer


What is the definition of computational complexity?

Computational complexity is the study of the resources required for solving computational problems, such as time and space

What is the difference between P and NP problems?

P problems can be solved in polynomial time while NP problems may or may not be solvable in polynomial time

What is the traveling salesman problem?

The traveling salesman problem is a famous problem in computer science that asks for the shortest possible route that visits a given set of cities exactly once and returns to the starting city

What is the definition of NP-complete problems?

NP-complete problems are problems in the set of NP that are at least as difficult as the hardest problems in NP

What is a reduction?

A reduction is a method used to show that one problem is at least as difficult as another problem, and is a fundamental tool used in complexity theory

What is the time complexity of the bubble sort algorithm?

The time complexity of the bubble sort algorithm is O(n^2), making it inefficient for large datasets

What is the space complexity of the merge sort algorithm?

The space complexity of the merge sort algorithm is O(n), making it more memory efficient than other sorting algorithms such as quicksort

What is the definition of Big O notation?

Big O notation is used to describe the upper bound on the growth rate of a function, and is commonly used in computer science to describe the time and space complexity of algorithms

What is the definition of an exponential-time algorithm?

An exponential-time algorithm is an algorithm whose running time grows exponentially as the size of the input increases

What is the definition of an NP-hard problem?

An NP-hard problem is a problem that is at least as hard as the hardest problems in NP, and may or may not belong to the set of NP

What is the Cook-Levin theorem?

The Cook-Levin theorem states that the Boolean satisfiability problem is NP-complete

What is the difference between worst-case, best-case, and average-case time complexity?

Worst-case time complexity is the maximum amount of time an algorithm can take for any input of size n, best-case time complexity is the minimum amount of time an algorithm can take for any input of size n, and average-case time complexity is the expected amount of time an algorithm takes for any input of size n

What is the definition of a decision problem?

A decision problem is a computational problem that asks whether a given input satisfies a certain property, and has a yes or no answer

What is the definition of a search problem?

A search problem is a computational problem that asks for a solution that satisfies a certain property, and may have multiple valid outputs

What is the definition of a nondeterministic algorithm?

A nondeterministic algorithm is an algorithm that can explore multiple solutions simultaneously, and is commonly used in complexity theory to define the set of NP

What is the definition of computational complexity?

Computational complexity is the study of the resources required for solving computational problems, such as time and space

What is the difference between P and NP problems?

P problems can be solved in polynomial time while NP problems may or may not be solvable in polynomial time

What is the traveling salesman problem?

The traveling salesman problem is a famous problem in computer science that asks for the shortest possible route that visits a given set of cities exactly once and returns to the starting city

What is the definition of NP-complete problems?

NP-complete problems are problems in the set of NP that are at least as difficult as the hardest problems in NP

What is a reduction?

A reduction is a method used to show that one problem is at least as difficult as another problem, and is a fundamental tool used in complexity theory

What is the time complexity of the bubble sort algorithm?

The time complexity of the bubble sort algorithm is O(n^2), making it inefficient for large datasets

What is the space complexity of the merge sort algorithm?

The space complexity of the merge sort algorithm is O(n), making it more memory efficient than other sorting algorithms such as quicksort

What is the definition of Big O notation?

Big O notation is used to describe the upper bound on the growth rate of a function, and is commonly used in computer science to describe the time and space complexity of algorithms

What is the definition of an exponential-time algorithm?

An exponential-time algorithm is an algorithm whose running time grows exponentially as the size of the input increases

What is the definition of an NP-hard problem?

An NP-hard problem is a problem that is at least as hard as the hardest problems in NP, and may or may not belong to the set of NP

What is the Cook-Levin theorem?

The Cook-Levin theorem states that the Boolean satisfiability problem is NP-complete

What is the difference between worst-case, best-case, and average-case time complexity?

Worst-case time complexity is the maximum amount of time an algorithm can take for any input of size n, best-case time complexity is the minimum amount of time an algorithm can take for any input of size n, and average-case time complexity is the expected amount of time an algorithm takes for any input of size n

What is the definition of a decision problem?

A decision problem is a computational problem that asks whether a given input satisfies a certain property, and has a yes or no answer

What is the definition of a search problem?

A search problem is a computational problem that asks for a solution that satisfies a certain property, and may have multiple valid outputs

What is the definition of a nondeterministic algorithm?

A nondeterministic algorithm is an algorithm that can explore multiple solutions simultaneously, and is commonly used in complexity theory to define the set of NP

Share


Login to Save


Share



Login to Save


Explore Other Decks


Made for Grade 7

Information Technology: Objects in Electronic Spreadsheets


View Deck
Made for Grade 8

The French Revolution


View Deck
Made for Grade 8

Thinking Outside the Box


View Deck

Explore More