Concepts
5,907Terms and methods explained by more than one lecturer. Each opens at the minute it is taught.
Theory & Algos
253- ReductionA transformation of one problem into another to show hardness or solve it.
- Dynamic programmingA method for solving complex problems by breaking them down into simpler subproblems.
- NP-completeA problem is NP-complete if it is in NP and it is NP-hard.
- Turing machineA mathematical model of computation that manipulates symbols on a strip of tape according to a table of rules.
- Chernoff boundA tail bound providing exponential decay probabilities for sums of independent random variables.
- NPA class of problems where a solution can be verified in polynomial time.
- Union boundA probability rule stating that the probability of the union of multiple events is at most the sum of their individual probabilities.
- Discrete Fourier transformA mathematical transformation that decomposes a discrete signal into its constituent frequencies.
- Fast Fourier transformAn algorithm used to compute the discrete Fourier transform and its inverse.
- Approximation algorithmAlgorithms that run in polynomial time and find solutions that are guaranteed to be close to the optimal or satisfy a large fraction of constraints rather than being exact.
- Directed acyclic graphA DAG is a directed graph with no directed cycles.
- Probabilistic methodA technique used to prove the existence of a mathematical object with certain properties by showing that a randomly chosen object has positive probability of having those properties.
- Proof by inductionA proof technique used to establish that a statement holds for all natural numbers by showing a base case and an inductive step.
- InductionA proof technique where one proves a base case and that implies to conclude the proposition holds for all natural numbers.
- NP-hardA problem is NP-hard if every problem in NP reduces to it in polynomial time.
- AssociativityThe property where grouping of elements in a binary operation does not change the result.
- CompletenessThe property that if the input W is truly in the class, there exists a proof that causes the tester to accept with probability 1.
- Greedy algorithmAn algorithmic approach that makes the locally optimal choice at each stage with the intent of finding a global optimum.
- Linearity of expectationThe expected value of the sum of two random variables is equal to the sum of their individual expected values.
- Constraint satisfaction problemA problem defined by variables, domains, and constraints, where the goal is to find an assignment of values to variables that satisfies all constraints.
- DiagonalizationA proof technique involving simulation to construct an object that differs from every object in a given enumeration.
- PThe class of problems that can be solved in polynomial time.
- Divide and conquerAn algorithmic paradigm that breaks a problem into smaller subproblems of the same type, solves them recursively, and combines their results.
- Fermat's little theoremA theorem stating that aᵖ⁻¹ ≡ 1 pmod p for any prime and integer not divisible by .
- Stirling's formulaAn approximation for factorials given by .
- Unitary matrixA matrix whose columns form an orthonormal basis and whose conjugate transpose is its inverse.
- Markov's inequalityMarkov's inequality bounds the probability that a non-negative random variable is greater than or equal to a positive constant by the ratio of its expected value to that constant.
- Topological sortA linear ordering of vertices in a directed acyclic graph such that for every directed edge uv, vertex u comes before vertex v in the ordering.
- Decision treeThe representation of a Boolean function represented as a binary tree where internal nodes are labeled by variables and leaves are labeled by numbers.
- Randomized algorithmAn algorithm that employs a degree of randomness as part of its logic.
- LanguageA subset of all possible strings over an alphabet.
- Modular arithmeticA system of arithmetic for integers where numbers wrap around after reaching a certain value called the modulus.
- ConfigurationA complete description of the state of a Turing machine, including the current state, the tape contents, and the head position.
- IndirectionThe ability to map virtual addresses to physical addresses, which is completely controlled by the operating system.
- Grover's algorithmA quantum algorithm that solves the unstructured search problem (finding a 1 among N bits) in square root of N queries.
- Pairwise independenceA condition where any two particular events or random variables in a set are independent, even if the entire set is not mutually independent.
- Binary search treeA binary tree where every node has at most two children and satisfies the search invariant that the right subtree contains greater keys and the left subtree contains smaller keys.
- Diffie-Hellman key exchangeA cryptographic protocol that allows two parties to establish a shared secret over an insecure channel.
- Halting problemThe problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.
- Adjacency listA representation of a graph where each vertex stores a list of all vertices it is connected to by an edge.
- ExpectationExpectation or mean is the probability-weighted average of all values a random variable can take.
- Indicator functionA function that takes the value 1 if a condition is met and 0 otherwise.
- Interactive proofsA proof system where a prover and a verifier interact to establish the truth of a statement.
- NP-completenessA language B is NP-complete if it is in NP and every language in NP is polynomial-time reducible to B.
- AnthropoceneA proposed new geological epoch defined by the dominant influence of human activity on Earth's climate and ecosystems.
- Circuit complexityThe measure of the resources needed to compute a boolean function using logic circuits, specifically evaluated as family sizes for languages.
- Computational complexityThe study of the resources, such as time and space, required to solve computational problems.
- ConsciousnessConsciousness comprises what you see, hear, feel, and dream, with dreams being conscious and dreamless sleep not.
- CryptographyThe art and science of scrambling and encrypting information so that it can be transmitted securely.
- Dijkstra's algorithmAn algorithm for finding the shortest paths between nodes in a graph with non-negative edge weights.
- Edit distanceThe minimum number of edits including insertions, deletions, or substitutions needed to make a read exactly match a reference segment.
- EncodingThe process of mapping mathematical objects into strings of bits or alphabet characters so they can be operated on by algorithms.
- Network flowA collection of problems associated with maximizing the amount of commodities that can push through a network with capacities.
- Optimal substructureA property of a problem where an optimal solution to the problem contains optimal solutions to subproblems.
- TreeA connected and acyclic graph is called a tree.
- Time hierarchy theoremA theorem stating that giving a Turing machine more time allows it to solve strictly more problems.
- Exponential time hypothesisThe assumption that 3SAT cannot be solved in sub-exponential time for some .
- Cook-Levin theoremA theorem stating that every language in NP reduces in polynomial time to CIRCUIT-SAT.
- Decision problemAny problem with a yes or no answer.
- BPPThe class of languages decidable by a probabilistic polynomial-time Turing machine with an error probability of at most 1/3.
- Hamming weightThe number of non-zero elements in a string, which for binary strings is the number of ones.
- PSPACEThe class of decision problems solvable by a Turing machine using a polynomial amount of space.
- Configuration graphA directed graph whose vertices are all possible configurations of a Turing machine on an input and whose edges represent valid state transitions.
- DerandomizationThe process of replacing random bits in an algorithm with pseudorandom strings generated deterministically from a short seed.
- Context-free grammarA formal grammar used to generate all possible strings in a given formal language.
- CutA partition of the vertices of a flow network into two sets, one containing the source and the other containing the sink.
- Interactive proof systemA generalization of NP where an all-powerful prover interacts with a probabilistic verifier over multiple rounds.
- NondeterminismA computational model where a machine can have multiple possible next states at any given step.
- Search problemA computational problem where there can be multiple correct answers or no answer at all.
- Unique games conjectureA conjecture stating that for all delta, it is NP-hard to distinguish between Label-Cover instances where almost all constraints can be satisfied versus instances where at most a delta fraction can be satisfied, even when the projection constraints are bijections.
- Universal Turing machineA Turing machine that takes a description of a machine and input and simulates its execution.
- Graph isomorphism problemThe computational problem of determining whether two finite graphs are isomorphic, meaning one can be transformed into the other by permuting its vertices.
- Hamiltonian pathA path in a directed graph that visits every node exactly once.
- Max-flow min-cut theoremThe theorem stating that the maximum flow in a network is equal to the capacity of the minimum cut.
- Post-quantum cryptographyCryptographic algorithms that are secure against a cryptanalytic attack by a quantum computer.
- Probabilistic Turing machineA PTM is a variant of a nondeterministic Turing machine where each computation step has 1 or 2 possible choices, with 50% probability assigned when there are two choices.
- Quadratic convergenceA rate of convergence where the number of correct digits of precision doubles at each iteration step.
- RelaxationThe fundamental operation in shortest path algorithms where we continually reduce estimated path distance values down to the true shortest path length.
- TableauA table representing the computation history of a Turing machine on an input.
- 3SATThe problem of checking if a given CNF formula with at most three literals per clause is satisfiable.
- All pairs shortest pathsThe problem of finding the shortest path weights between all pairs of vertices in a directed graph.
- Amortized analysisAn analysis technique where we bound the total cost of a sequence of operations rather than the individual running time of each operation.
- Asymptotic notationNotation used to describe how a function grows in the limit.
- Bernoulli random variableA random variable that takes the value 1 with probability p and 0 with probability 1-p.
- Bit vectorAn array of bits representing a set, where a 1 indicates an element is present and a 0 indicates it is absent.
- Church-Turing thesisAny real-world algorithm can be simulated or compiled by Turing machines.
- ClauseAn OR (disjunction) of literals.
- Complex systemSystems composed of individual pieces interacting with each other to produce macroscopic phenomena.
- EncryptionThe art and tool of hiding information by transforming a plain message into an encrypted message using keys.
- Euler's theoremA generalisation of Fermat's Little Theorem stating that raised to the power of is congruent to modulo when and are coprime.
- GadgetA substructure in a reduction that converts features of an input problem into corresponding features of an output problem.
- HeapA tree-based data structure satisfying the heap property, where parent nodes are ordered relative to their children.
- Inductive hypothesisThe assumption that the -th statement is true when proving the -th statement.
- Linear programAn optimization problem with linear variables, a linear cost function to minimize or maximize, and linear constraints.
- LiteralA variable or its negation in a Boolean formula.
- Little o notationA notation used to describe the limiting behavior of a function relative to another, indicating it grows slower.
- Minimum spanning treeGiven a graph G and edge weights, a minimum spanning tree is a spanning tree of minimum total weight.
- One-to-one correspondenceA mapping between two sets of points where each point in one set is paired with exactly one point in the other set.
- PathThe language consisting of directed graphs that contain a path between two specified nodes.
- Perfect matchingA matching in a graph where every vertex is incident to exactly one edge of the matching.
- Polynomial interpolationThe process of finding a polynomial that passes through a given set of points.
- Polynomial time mapping reductionA mapping reduction that runs in polynomial time, meaning there exists a polynomial-time computable function R such that x is in one language if and only if R(x) is in the other.
- Pseudo random number generatorGenerators of pseudo random numbers that are computed and deterministic.
- Public key encryptionA method of secure communication where a secret is encrypted using the recipient's public key, ensuring only the recipient can decrypt it.
- RecurrenceAn equation that expresses a value in terms of one or more smaller instances of the same problem.
- SoundnessThe property that if the input W is far from being in the class, then no proof will be convincing and the tester rejects with high probability.
- Spanning treeA spanning tree of a graph G is a subset of edges of G that form a tree and hit all vertices of G.
- Vertex coverA set of vertices that intersects or meets all the edges in the graph.
- Zero-knowledge proofsAn interactive proof system where a prover convinces a verifier of a statement's truth without leaking any information beyond the fact that the statement is true.
- PCP theoremA theorem stating that approximating Max-E3Sat to within some constant factor strictly less than 1 is NP-hard.
- Strong exponential time hypothesisThe assumption that for any delta, there exists a k such that k-SAT requires two to the one minus delta times n time.
- Berry-Esseen theoremA theorem used to bound the error in the normal approximation of a sum of independent random variables.
- Discrete logarithm problemThe computational problem of finding the exponent given in a cyclic group.
- Polynomial time reductionA method to transform one problem into another using an algorithm that runs in polynomial time.
- Savitch's theoremA theorem stating that any problem solvable by a non-deterministic Turing machine in space is solvable by a deterministic Turing machine in space.
- TQBFThe language of true quantified boolean formulas.
- ArithmetizationThe process of converting a Boolean formula into a polynomial whose values match the Boolean formula on Boolean inputs.
- Circuit SATThe problem of determining if there exists an input to a boolean circuit that makes the circuit output 1.
- DeciderA Turing machine that halts on every input.
- P/polyThe complexity class containing all languages decidable by polynomial-size circuit families.
- Schwartz-Zippel lemmaA lemma stating that a non-zero multivariate polynomial over a finite field evaluates to a non-zero value with high probability when given random inputs.
- Space hierarchy theoremA theorem stating that giving a Turing machine more space allows it to solve strictly more problems.
- Unitary transformationA linear transformation on a complex inner product space that preserves inner products, representing reversible quantum operations.
- Brute-force attackAn attack method that systematically tries all possible keys until the correct one is found.
- Dictator functionA Boolean function whose output depends only on a single input coordinate.
- EXPThe complexity class of problems solvable in exponential time, specifically 2 to the power of a polynomial in n.
- Extended Euclidean algorithmAn algorithm used to compute multiplicative inverses in prime fields.
- FactoringThe problem of finding the prime factors of a given integer.
- Non-determinismA computational model where the machine can be in multiple states or follow multiple paths simultaneously, accepting if at least one path reaches an accept state.
- Oracle Turing machineA Turing machine equipped with an additional oracle tape and oracle state that allows it to decide membership in a specified language in a single step.
- Polynomial hierarchyA hierarchy of complexity classes that generalize P, NP, and coNP using alternating quantifiers.
- Polynomial identity testingThe problem of checking whether two given algebraic circuits compute identical polynomials.
- Radix sortA sorting algorithm that sorts integers by processing their individual bits or digits from least significant to most significant using a stable sort.
- SATThe counting problem of determining the exact number of satisfying assignments for a given Boolean formula.
- Space complexityThe class of problems that can be decided using a bounded amount of tape cells as a function of the input size.
- Space constructible functionA function such that a Turing machine can compute the value using space.
- Tall-cache assumptionThe assumption that cache size is at least , meaning the cache is taller than it is wide.
- Time constructible functionA function is time constructible if there exists a Turing machine that, given , outputs in time.
- Word RAM modelA standard computational model where words of size proportional to can be processed in constant time.
- Advanced encryption standardA symmetric block cipher chosen as a standard by NIST to replace DES.
- Asymmetric cryptographyA cryptographic model where encryption and decryption use different keys, specifically a public key for encryption and a private key for decryption.
- Birthday paradoxA probability principle implying that an attack on a hash function requires roughly half the bit length of security steps to find a collision.
- Bounded-error probabilistic polynomial timeThe class of languages decided by a polynomial-time probabilistic Turing machine with an error probability of at most 1/3 on all inputs.
- ChainingA collision resolution technique where colliding keys in a hash table are stored together in a linked list.
- CNOT gateA 4x4 unitary quantum gate that applies a NOT operation to the target qubit if and only if the control qubit is in the state 1.
- Co-NPThe class of languages whose complements are in NP.
- Communication complexityThe study of computing functions when two parties are computing them and the thing that is measured is how much they need to communicate.
- Computable functionA function is computable if there is a Turing machine that halts with the function's output on its tape for any given input string.
- Data structure augmentationMaintaining extra information at every node of a data structure to support additional queries or properties efficiently during operations.
- Deutsch-Jozsa algorithmA deterministic quantum algorithm that distinguishes whether a boolean function is constant or balanced with a single query, providing an exponential speedup over classical deterministic algorithms.
- DiffusionAn atomic operation where the influence of each plaintext bit is spread over many ciphertext bits.
- Divide and conquer recurrenceRecurrences where you break the problem up into much smaller subproblems, like half the size or two-thirds the size.
- Fine-grained complexityThe study of exact running times and fine-grained differences within polynomial time complexity rather than just polynomial vs exponential.
- Flow conservationThe principle that for any vertex other than the source and sink, the total flow entering must equal the total flow leaving.
- Fourier coefficientThe coefficient of a specific monomial in the Fourier expansion of a function.
- Gadget reductionA reduction that translates instances of one problem to another using structural components called gadgets.
- Graph isomorphismThe computational problem of determining whether two finite graphs are isomorphic, known to be in NP.
- Leader electionThe process where exactly one process in a connected graph outputs a special leader signal.
- Log spaceComputation model where a two-tape Turing machine uses logarithmic space with a read-only input tape and a read/write work tape.
- Longest common subsequenceThe problem of finding the longest subsequence that is present in two given strings in the same relative order, but not necessarily contiguous.
- Mutual independenceRandom variables are mutually independent if the joint probability of any combination of their values is equal to the product of their individual probabilities.
- NLThe class of decision problems solvable by a non-deterministic Turing machine using logarithmic space.
- NPSPACEThe class of decision problems solvable by a nondeterministic Turing machine using a polynomial amount of space.
- One-time padA perfectly secure encryption scheme where the secret key is a uniformly random string of the same length as the message and is used only once.
- PaddingA complexity theory trick of artificially changing the input length of a language or problem.
- Parity check matrixA parity check matrix H for a code C is a matrix whose rows are orthogonal to every codeword in C.
- PermutationA function from a set to itself such that no two numbers are mapped to the same value.
- Probabilistically checkable proofsA type of proof system where a reviewer can verify a proof with high confidence by spot-checking only a constant number of symbols randomly.
- Quantum measurementThe process of observing a quantum state, which causes the state to collapse into a specific basis state with a probability determined by the square of its amplitude.
- ReducibilityIf we have two languages or problems A and B, then A is reducible to B means that we can use B to solve A.
- RelativizationThe property of simulation results holding equally well when both machines are given access to the same oracle.
- RingAn algebraic structure extending groups by adding multiplication, though not all elements necessarily have a multiplicative inverse.
- Round functionThe repeating function applied for 80 rounds in SHA-1, consisting of additions, bit shifts, and Boolean functions.
- Schönhage-Strassen algorithmAn asymptotically fast multiplication algorithm for large integers running in O(n log n log log n) time.
- Symmetric cryptographyA cryptographic scheme where the same secret key is used for both encryption and decryption.
- Table doublingA dynamic array resizing strategy where the array capacity is doubled whenever it runs out of space.
- TrieA rooted tree whose child branches are labeled with letters in the alphabet, used here to represent strings as root-to-leaf paths.
- A complexity class in the polynomial hierarchy corresponding to .
- Average-case hardnessThe property that circuits of a given size are wrong on almost all inputs, performing as badly as random guessing.
- AVL treeAVL trees require the heights of the left and right children of every node to differ by at most plus or minus one.
- Backward edgeAn edge that connects a node to one of its ancestors in the depth-first search tree.
- BadnessAn aesthetic cost function that quantifies how undesirable a specific line break configuration is.
- Bellman-Ford algorithmAn algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph supporting negative edge weights.
- Chromatic numberThe minimum number of colors needed to color a graph such that adjacent nodes have different colors.
- Class PThe class P consists of all problems that can be solved in time that is bounded by a polynomial of the input size.
- Collision resistanceA hash function property stating it is infeasible to find any two distinct inputs x and x' that produce the same hash output.
- Complexity theoryComplexity theory investigates what is computable in practice, focusing on resources like time and space required by algorithms.
- CompositesThe decision problem of determining whether a given natural number is composite (not prime and greater than 1).
- Computability theorySort of like a precursor to complexity theory that asks what computational tasks can be solved at all.
- Computational complexity theoryThe study of the most efficient ways to solve computational tasks with respect to various resources.
- coNLThe class of decision problems whose complement is in NL.
- coNPThe class of languages whose complements are in NP.
- coNP-completeA problem is coNP-complete if it is in coNP and every other coNP problem is polynomial-time reducible to it.
- coRPThe class of languages whose complements are in RP, allowing false negative errors instead of false positive errors.
- Counting sortA sorting algorithm that counts the number of occurrences of each key to construct the sorted list in linear time.
- Cross edgeAn edge that goes between two nodes in the DFS tree where neither is an ancestor of the other.
- Diagonalization methodA proof technique similar to Cantor's diagonal argument used to show uncountability or undecidability.
- Diameter of a graphThe maximum distance between any pair of vertices in the graph.
- Diffie-Hellman problemThe problem of computing given and without knowing and .
- Error termThe difference between two approximations in a Taylor expansion, bounded to analyze the approximation quality.
- Euler tourA walk that traverses every edge exactly once and starts and finishes at the same vertex.
- Exact 3-satisfiability3SAT with the restriction that every clause has exactly three distinct literals and three distinct variables.
- Finite fieldA field is a set of numbers in which we can add, subtract, multiply and divide, with a finite number of elements.
- Floyd-Warshall algorithmAn algorithm that computes shortest paths between all pairs of vertices in a graph using three nested loops.
- Forward edgeAn edge that connects a node to one of its descendants in the depth-first search tree.
- Freivalds' algorithmA randomized algorithm that verifies whether the product of two matrices is equal to a third matrix in time.
- Hardness versus randomnessA paradigm in complexity theory showing that computational hardness can be traded for pseudorandomness to derandomize efficient probabilistic algorithms.
- Harmonic numberThe nth harmonic number is the sum of the reciprocals of the first n numbers.
- Immerman-Szelepcsényi theoremA theorem in complexity theory stating that non-deterministic space is closed under complement.
- Integral approximation of sumsBounding sums like log factorials by comparing them with the area of rectangles and under curve integrals.
- Inverse elementAn element for every group element that, when combined with it via the group operation, yields the neutral element.
- Irreducible polynomialA polynomial of degree at least 2 that cannot be factored as a product of two lower-degree polynomials.
- Karatsuba algorithmA fast multiplication algorithm that reduces the number of recursive multiplication operations from 4 to 3.
- Knapsack problemA problem of finding a subset of weights that sums to a particular target sum, which is NP-complete in its general form.
- Linear probingA probing strategy in open addressing where the hash function adds the probe number sequentially to an ordinary hash function.
- Log-space reductionA mapping reduction where the reduction function is computable in logarithmic space.
- LP dualityA principle where every linear maximization program has a dual minimization program whose optimal value provides an upper bound on the primal.
- Mathematical proofProofs are strings satisfying some special syntactic property derived from axioms using inference rules.
- Median findingThe problem of finding the median or an element of a specific rank in a set of numbers in better than time.
- Multi-tape Turing machineA Turing machine variant that has one or more tapes, where the input is on the first tape and the others are initially blank work tapes.
- Natural proofsA framework describing lower bound techniques that are large and constructible.
- Newton's method for divisionDivision reduces to computing 1 over y by solving the equation yz = 1 using Newton's method, then performing a multiplication with x.
- NL-completenessA language is NL-complete if it is in NL and every language in NL is log-space reducible to it.
- Non-deterministic algorithmAn algorithm that can make non-deterministic choices, such as branching into multiple paths using 'go-to-both' operations.
- Non-deterministic log spaceA complexity class of decision problems solvable by a non-deterministic Turing machine using logarithmic space.
- Non-deterministic Turing machineA Turing machine that can have multiple possible next states from a given state and input symbol.
- Nondeterministic timeNondeterministic time NTIME(f(n)) is the class of languages decidable by a nondeterministic Turing machine within f(n) time steps.
- Nth roots of unityNumbers that yield 1 when raised to the nth power, uniformly spaced around the unit circle in the complex plane.
- Order of an elementThe cycle length or number of distinct values reached when computing successive powers of an element in a group.
- Partition problemThe problem of partitioning a set of items with weights into two subsets such that the maximum weight of the two subsets is minimized.
- Peak findingAn algorithmic problem of finding an element in an array that is greater than or equal to its immediate neighbors.
- Polynomial evaluationThe process of computing a polynomial's values given its coefficients representation.
- Polynomial hierarchy collapseIf , the polynomial hierarchy collapses, implying that higher classes like collapse to P.
- Potential methodA technique for amortized analysis that maps a data structure's state to a potential function value to pay for costly operations.
- Predecessor problemThe problem of maintaining a set of elements to support insert, delete, predecessor, and successor queries.
- Probabilistic algorithmAn algorithm that uses randomness as part of its logic to solve problems.
- Pseudo-random generatorA generator that takes a short seed of log n bits and expands it to n bits such that efficient polynomial-time machines cannot distinguish it from true randomness.
- PSPACE-completenessA problem is PSPACE-complete if it is in PSPACE and every problem in PSPACE can be polynomial-time reduced to it.
- Public key cryptographyCryptographic systems providing automated authentication without secrecy and a way to extract a shared secret for encrypted communication.
- Push operationThe operation of adding a new symbol onto the top of a stack, which pushes existing symbols down.
- Randomized polynomial timeA complexity class for languages recognized by a probabilistic Turing machine in polynomial time with one-sided error.
- Stable marriage problemThe problem of finding a stable matching between two equally-sized sets of elements given preference lists for each element.
- Symmetric differenceThe set of all elements that are in either of the two sets, but not in their intersection.
- TAUTOLOGYA language consisting of all boolean formulas where every possible assignment of variables makes the formula true.
- Time complexityThe total time required for an algorithm to complete its execution in the worst case.
- Time-space relationshipThe containment relationship between time complexity classes and space complexity classes.
- Transdichotomous RAM modelA model of computation where running times only depend on and work for all word sizes .
- Transitive closureThe reachability relation between vertices in a graph, computed via repeated squaring or specialised matrix operations.
- Tree edgeTree edges are edges that lead to an unvisited vertex during a depth-first search, forming a directed tree or forest.
- Van Emde Boas treeA tree-based data structure supporting predecessor queries in Θ(log log u) time using space.
- Verification algorithmA deterministic algorithm that takes a problem input and a certificate, and checks in polynomial time whether the certificate proves a YES answer.
- Worst-case hardnessThe assumption that a problem like 3-SAT does not have a small circuit that gets it correct on every input.
- Zero-error probabilistic polynomial timeZPP is the complexity class of problems solvable by a probabilistic Turing machine in expected polynomial time with zero error.