Computational Complexity & Fourier Transforms - Vocabulary Flashcards

Vocabulary flashcards covering key terms from the lecture on computational complexity, problem reductions, complexity classes, optimization vs. decision problems, and the DFT/FFT.

Computational complexity

The study of the time (temporal) and space (memory) resources required by an algorithm; depends on both the algorithm and the data structures used.

Temporal complexity

The number of basic operations an algorithm performs as a function of input size N.

Spatial complexity

The memory used beyond the input size N to complete an algorithm.

Decision problem

A problem whose answer is yes or no, used to analyze and compare problems and study P vs NP.

P (Polynomial Time)

Class of decision problems solvable by a deterministic algorithm in time polynomial in input size.

NP (Nondeterministic Polynomial Time)

Class of problems where a proposed solution can be verified in polynomial time by a deterministic algorithm.

NP-Hard

Problems that are at least as hard as the hardest problems in NP; may not be in NP; solving them efficiently would solve all NP problems.

NP-Complete

Problems that are both in NP and NP-Hard; solving any one in polynomial time would imply P = NP.

Reduction

Transforming one problem into another so that solving the second helps solve the first.

Optimization problem

A problem that seeks the best possible solution (e.g., maximum value, minimum time).

Decision version of an optimization problem

The yes/no version obtained by adding a threshold to the optimization goal.

Shortest path (optimization)

Find the minimum-length path between two cities.

Decision version of shortest path

Is there a path between two cities with length at most k?

Largest non-overlapping task set

Optimization version that aims to maximize the number of non-overlapping tasks.

Decision version: ≥ k non-overlapping tasks

Is there a non-overlapping task set of size at least k?

Knapsack problem

Choose items to maximize value without exceeding a weight limit.

Decision version of Knapsack

Can we pack items with total value at least k without exceeding weight W?

Chromatic number

The smallest number of colors needed to color a graph so that adjacent vertices have different colors.

Decision version of graph coloring

Can the graph be colored with at most k colors?

Unsolvable (uncomputable)

Problems for which no algorithm can give correct answers for all inputs.

Halting problem

The problem of determining whether a program will halt on a given input; proven undecidable by Turing.

DFT (Discrete Fourier Transform)

Transform that converts a finite sequence from time domain to frequency domain; naively O(n²) to compute.

FFT (Fast Fourier Transform)

Efficient algorithm to compute the DFT in O(n log n), typically via divide-and-conquer.

Radix-2 FFT

FFT variant requiring input length to be a power of 2 and using even/odd index splitting.

Cooley–Tukey FFT

1965 algorithm that popularized FFT by recursively factoring the DFT to achieve O(n log n).