SCC.121 Algorithms and Complexity - P vs NP Introduction

Flashcards covering the concepts of P vs NP, time complexity, and related problems from an introductory lecture.

What type of problems were students requesting more practice questions for?

Time complexity problems

What does the acronym TSP stand for?

Travelling Salesperson Problem

What is the goal of the Travelling Salesperson Problem (TSP)?

To find the shortest route for a salesperson to visit all cities exactly once and return to the starting point.

What is the time complexity of a brute-force solution to the TSP?

O(n!), where n is the number of cities

List examples of growth rates of functions from slowest to fastest?

Constant, Logarithmic, Linear, N log N, Quadratic, N^2 log N, Cubic, Polynomial, Exponential, Factorial

What is the primary distinction between polynomial and super-polynomial functions?

Polynomial functions are bounded from above by n^c, while super-polynomial functions grow faster than any polynomial function.

Define 'intractable' in the context of algorithms.

A problem is called intractable if there is no efficient (polynomial-time) algorithm that solves it.

Define 'tractable' in the context of algorithms.

A problem is called tractable if there is an efficient (polynomial-time) algorithm that solves it.

Why are computer speed improvements alone not sufficient for inefficient algorithms?

The less efficient the algorithm, the less a faster computer can improve the size of a problem that can be solved in a fixed time. The jump in computational requirements happens very fast for exponential algorithms.

What is 'P' in the context of complexity theory?

Problems for which there exists a polynomial-time algorithm.

Give examples of problems that belong to the 'P' complexity class?

Binary Search, Linear Search, Breadth-First Search, Dijkstra’s Algorithm, Sorting Algorithms, Minimum Spanning Tree

What is 'EXP' in the context of complexity theory?

Problems for which there is an exponential-time algorithm.

What type of complexity is generally considered intractable?

Algorithms that are exponential or worse (such as factorial) are generally considered intractable.

List examples of problems with no known polynomial-time solution?

Traveling Salesperson (TSP), SAT, Knapsack, 3-coloring, Clique, Minesweeper, Sudoku, Monkey Puzzle

What is 'R' in the context of computational difficulty?

Problems solvable in finite time.

Why is factoring integers considered a computationally difficult problem?

Classical algorithms for factoring integers require exponential time in the worst case. Some widely used cryptographic algorithms, such as RSA, rely on it being a hard problem to solve as the numbers get bigger.

What is NP?

NP: decision problems that can be checked in polynomial time

Explain the P vs NP problem?

Can every problem whose solution can be quickly verified by a computer also be quickly solved by a computer? In other words, does P=NP?

What is the potential impact if it is proven that P = NP?

Decrypt current internet communication, revolutionize AI, faster computations, cure for cancer, etc.

What is the potential impact if it is proven that P ≠ NP?

Prove that for some questions there is no clever shortcut to find the right answer and understand more about computation

List some problems that involve searching and finding the 'needle in a haystack'?

Traveling salesperson (TSP), SAT, Knapsack, 3-coloring, Clique, Minesweeper, Sudoku, monkey puzzle, scheduling, protein folding

What is the Clay Mathematics Institute known for?

Offering $1,000,000 for the solution to each of the Seven Millennium Prize Problems, including P vs NP.

What can be done to address an intractable problem?

Use heuristics, solve problem approximately, use an exponential time algorithm, solve a different problem.