Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| polynomial-time algorithms | on inputs of size n, their worst-case running time is O(nk) for some constant k.
(See page 966)
|
 |
|
|
| Euler tour | of a connected, directed graph G = (V, E) is a cycle that traverses each edge of G exactly once, although it may visit a vertex more than once.
(See page 966)
|
|
|
|
| hamiltonian cycle | of a directed graph G = (V, E) is a simple cycle that contains each vertex in V.
(See page 967)
|
|
|
|
| satisfiable | A boolean formula is satisfiable if there is some assignment of the values 0 and 1 to its variables that causes it to evaluate to 1.
(See page 967)
|
|
|
|
| k-conjuctive normal form | a boolean formula is in k-conjuctive normal form, or k-CNF, if it is the AND of clauses of ORs of exactly k variables or their negations.
(See page 967)
|
|
|
|
| NP-complete | Informally, a problem is in the class NPC - and we refer to it as being NP-complete - if it is in NP and is as "hard" as any problem in NP.
(See page 968)
|
|
|
|
| optimization problems | each feasible (i.e., "legal") solution has an associated value, and we wish to find the feasible solution with the best value.
(See page 968)
|
|
|
|
| decision problems | the answer is simply "yes" or "no" (or, more formally, "1" or "0")
(See page 969)
|
|
|
|
| instance | input to a particular problem
(See page 969)
|
|
|
|
| reduction algorithm | a procedure that transforms any instance α of A into some instance β of B with the following characteristics:- The transformation takes polynomial time.
- The answers are the same. That is, the answer for α is "yes" if and only if the answer for β is also "yes."
(See page 970)
|
|
|
|
| abstract problem | defined for Q to be a binary relation on a set I of problem instances and a set S of problem solutions.
(See page 972)
|
|
|
|
| optimization problems | in which some value must be minimized or maximized.
(See page 972)
|
|
|
|
| encoding | of a set S of abstract objects is a mapping e from S to the set of binary strings. The codomain of e need not be binary strings over a finite alphabet having at least 2 symbols will do.
(See page 973)
|
|
|
|
| concrete problem | a problem whose instance set is the set of binary strings
(See page 973)
|
|
|
|
| polynomial-time solvable | A concrete problem is polynomial-time solvable if there exists an algorithm to solve it in time O(nk) for some constant k.
(See page 973)
|
|
|
|
| complexity class P | The set of concrete decision problems that are polynomial-time solvable.
(See page 973)
|
|
|
|
| polynomial-time computable | A function f : {0, 1}* → {0, 1}* is polynomial-time computable if there exists a polynomial-time algorithm A that, given any input
x ∈ {0, 1}*, produces as output f(x).
(See page 974)
|
|
|
|
| polynomially related | For some set I of problem instances, we say that two encodings e1 and e2 are polynomially related if there exist two polynomial-time computable functions f12 and f21 such that for any i ∈ I, we have
f12(e1(i)) = e2(i) and f21(e2(i)) = e1(i). That is, the encoding e2(i) can be computed from the encoding e1(i) by a polynomial-time algorithm, and vice versa. If two encodings e1 and e2 of an abstract problem are polynomially related, whether the problem is polynomial-time solvable or not is independent of which encoding we use.
(See page 974)
|
|
|
|
| noninstance | of an encoding e is a string x ∈ {0, 1}* such that there is no instance i for which e(i) = x.
(See page 974)
|
|
|
|
| alphabet | Ε is a finite set of symbols.
(See page 975)
|
|
|
|
| language | L over Ε is any set of strings made up of symbols from Ε.
(See page 975)
|
|
|
|
| concatenation | of two languages L1 and L2 is the language L = {x1x2 : x1 ∈ L1 and x2 ∈ L2}.
(See page 976)
|
|
|
|
| closure or Kleene star | of a language L is the language L* = {ε} ∪ L ∪ L2 ∪ L3 ∪ . . . , where Lk is the language obtained by concatenating L to itself k times.
(See page 976)
|
|
|
|
| accepts | An algorithm A accepts a string x ∈ {0, 1}* if, given input x, the algorithm's output A(x) is 1.
(See page 976)
|
|
|
|
| accepted | The language accepted by an algorithm A is the set of strings
L = {x ∈ {0,1}* : A(x) = 1}, that is, the set of strings that the algorithms accepts.
(See page 976)
|
|
|
|
| rejects | An algorithm A rejects a string x if A(x) = 0.
(See page 976)
|
|
|
|
| decided | A language L is decided by an algorithm A if every binary string in L is accepted by A and every binary string not in L is rejected by A.
(See page 976)
|
|
|
|
| accepted in polynomial time | A language L is accepted in polynomial time by an algorithm A if it is accepted by A and if in addition there is a constant k such that for any length-n string x ∈ L, algorithm A accepts x in time O(nk).
(See page 976)
|
|
|
|
| decided in polynomial time | A language L is decided in polynomial time by an algorithm A if there is a constant k such that for any length-n string x ∈ {0,1}*, the algorithm correctly decides whether x ∈ L in time O(nk). Thus, to accept a language, an algorithm need only worry about strings in L, but to decide a language, it must correctly accept or reject every string in {0,1}*.
(See page 976)
|
|
|
|
| complexity class | Informally defined as a set of languages, membership in which is determined by a complexity measure, such as running time, of an algorithm that determines whether a given string x belongs to language L. The actual definition of a complexity class is somewhat more technical.
(See page 977)
|
|
|
|
| hamiltonian | A graph that contains a hamiltonian cycle is said to be hamiltonian; otherwise, it is nonhamiltonian.
(See page 979)
|
|
|
|
| hamiltonian-cycle problem | "Does a graph G have a hamiltonian cycle?" can be defined as a formal language: HAM-CYCLE = {⟨G⟩ : G is a hamiltonian graph}.
(See page 979)
|
|
|
|
| verification algorithm | defined as being a two-argument algorithm A, where one argument is an ordinary input string x and the other is a binary string y called a certificate.
(See page 980)
|
|
|
|
| verifies | A two-argument algorithm A verifies an input string x if there exists a certificate y such that A(x, y) = 1.
(See page 980)
|
|
|
|
| language verified | The language verified by a verification algorithm A is L = {x ∈ {0,1}* : there exists y ∈ {0,1}* such that A(x, y) = 1}. Intuitively, an algorithm A verifies a language L if for any string x ∈ L, there is a certificate y that A can use to prove that x ∈ L. Moreover, for any string x ∉ L, there must be no certificate proving that x ∈ L.
(See page 981)
|
|
|
|
| complexity class NP | the class of languages that can be verified by a polynomial-time algorithm. The name "NP" stands for "nondeterministic polynomial time." The class NP was originally studied in the context of nondeterminism, but this book uses the somewhat simpler yet equivalent notion of verification. A language L belongs to NP if and only if there exist a two-input polynomial-time algorithm A and constant c such that L = {x ∈ {0,1}* : there exists a certificate y with |y| = O(|x|c) such that A(x, y) = 1}. We say that algorithm A verifies language L in polynomial time.
(See page 981)
|
|
|
|
| hamiltonian path | in a graph is a simple path that visits every vertex exactly once.
(See page 983)
|
|
|
|
| tautology | Let φ be a boolean formula constructed from the boolean input variables x1, x2, . . . , xk, negations (¬), AND's(^), OR's(V), and parentheses. The formula φ is a tautology if it evaluates to 1 for every assignment of 1 and 0 to the input variables.
(See page 983)
|
|
|
|
| polynomial-time reducible | A language L1 is polynomial-time reducible to a language L2, written L1 ≤P L2, if there exists a polynomial-time computable function
f : {0,1}* → {0,1}* such that for all x ∈ {0,1}*,x ∈ L1 if and only if f(x) ∈ L2. We call the function f the reduction function, and a polynomial-time algorithm F that computes f is called a reduction algorithm.
(See page 984)
|
|
|
|
| NP-complete | A language L ⊆ {0,1}* is NP-complete if- L ∈ NP, and
- L′ ≤P L for every L′ ∈ NP.
(See page 986)
|
|
|
|
| NP-hard | If a language L satisfies property 2 of NP-complete, but not necessarily property 1, we say that L is NP-hard.
(See page 986)
|
|
|
|
| boolean combinational element | any circuit element that has a constant number of boolean inputs and outputs and that performs a well-defined function.
(See page 987)
|
|
|
|
| logic gates | The boolean combinational elements that we use in the circuit-satisfiability problem which compute a simple boolean function.
(See page 987)
|
|
|
|
| NOT gate | (or inverter) takes a single binary input x, whose value is either 0 or 1, and produces a binary output z whose value is opposite that of the input value.
(See page 987)
|
|
|
|
| AND & OR gates | each gate takes two binary inputs x and y and produces a single binary output z
(See page 987)
|
|
|
|
| truth table | describes the operation of the logic gates, and of any boolean combinational element. Gives the outputs of the combinational element for each possible setting of the inputs.
(See page 987)
|
|
|
|
| boolean combinational circuit | consists of one or more boolean combinational elements interconnected by wires.
(See page 988)
|
|
|
|
| fan-out | the number of element inputs fed by a wire.
(See page 988)
|
|
|
|
| circuit input | If no element output is connected to a wire, the wire is a circuit input, accepting input values from an external source.
(See page 988)
|
|
|
|
| circuit output | If no element input is connected to a wire, the wire is a circuit output, providing the results of the circuit's computation to the outside world.
(See page 988)
|
|
|
|
| truth assignment | for a boolean combinational circuit is a set of boolean input values. For a boolean formula φ it is a set of values for the variables of φ.
(See page 988 & 996)
|
|
|
|
| satisfiable | a one-output boolean combinational circuit is satisfiable if it has a satisfying assignment. A formula with a satisfying assignment is a satisfiable formula.
(See page 988)
|
|
|
|
| satisfying assignment | for a boolean combinational circuit it is a truth assignment that causes the output of the circuit to be 1. For a boolean formula it is a truth assignment that causes it to evaluate to 1.
(See page 988)
|
|
|
|
| circuit-satisfiability problem | "Given a boolean combinational circuit composed of AND, OR, and NOT gates, is it satisfiable?"
(See page 989)
|
|
|
|
| program counter | special memory location, keeps track of which instruction is to be executed next.
(See page 990)
|
|
|
|
| configuration | any particular state of computer memory
(See page 991)
|
|
|
|
| complete | A language L is complete for a language class C with respect to polynomial-time reductions if L ∈ C and L′ ≤P L for all L′ ∈ C.
(See page 994)
|
|
|
|
| (formula) satisfiability | formulate the problem in terms of the language SAT as follows. An instance of SAT is a boolean formula φ composed of- n boolean variables: x1, x2, . . . , xn;
- m boolean connectives: any boolean function with one or two inputs and one output, such as ^ (AND), V (OR), ¬ (NOT), → (implication), ↔ (if and only if); and
- parentheses. (Without loss of generality, we assume that there are no redundant parentheses, i.e., there is at most one pair of parentheses per boolean connective.)
(See page 996)
|
|
|
|
| literal | in a boolean formula is an occurence of a variable or its negation.
(See page 999)
|
|
|
|
| conjuctive normal form (CNF) | A boolean formula in this form is expressed as an AND of clauses, each of which is the OR of one or more literals.
(See page 999)
|
|
|
|
| 3-conjunctive normal form (3-CNF) | A boolean formula is in this form if each clause has exactly three distinct literals.
(See page 999)
|
|
|
|
| disjunctive normal form (DNF) | an OR of AND's
(See page 1000)
|
|
|
|
| clique | in an undirected graph G = (V, E) is a subset V′ ⊆ V of vertices, each pair of which is connected by an edge in E. In other words, a clique is a complete subgraph of G.
(See page 1003)
|
|
|
|
| size | of a clique is the number of vertices it contains. The size of a vertex cover is the number of vertices in it.
(See page 1003 & 1006)
|
|
|
|
| clique problem | the optimization problem of finding a clique of maximum size in a graph. As a decision problem, we ask simply whether a clique of given size k exists in the graph.
(See page 1003)
|
|
|
|
| vertex-cover | of an undirected graph G = (V, E) is a subset V′ ⊆ V such that if
(u, v) ∈ E, then u ∈ V′ or v ∈ V′ (or both). That is, each vertex "covers" its incident edges, and a vertex cover for G is a set of vertices that covers all the edges in E.
(See page 1006)
|
|
|
|
| vertex-cover problem | to find a vertex cover of minimum size in a given graph. Restating this optimization problem as a decision problem, we wish to determine whether a graph has a vertex cover of a given size k. As a language, we define VERTEX-COVER = {⟨G, k⟩ : graph G has a vertex cover of size k}.
(See page 1006)
|
|
|
|
| widget | a piece of a graph that enforces certain properties.
(See page 1008)
|
|
|
|
| selector vertices | The only other vertices in V′ other than those of widgets are selector vertices s1, s2, . . . , sk. We use edges incident on selector vertices in G′ to select the k vertices of the cover in G.
(See page 1009)
|
|
|
|
| traveling-salesman problem | closely related to the hamiltonian-cycle problem. A salesman must visit n cities. Modeling the problem as a complete graph with n vertices, we can say that the salesman wishes to make a tour, or hamiltonian cycle, visiting each city exactly once and finishing at the city he starts from. There is an integer cost c(i, j) to travel from city i to city j, and the salesman wishes to make the tour whose total cost is minimum, where the total cost is the sum of the individual costs along
the edges of the tour.
(See page 1012)
|
|
|
|
| subset-sum problem | given a finite set S ⊂ N and a target t ∈ N. We ask whether there is a subset S′ ⊆ S whose elements sum to t.
|
|
|
|
| subgraph-isomorphism problem | takes two graphs G1 and G2 and asks whether G1 is isomorphic to a subgraph of G2.
(See page 1017)
|
|
|
|
| 0-1 integer-programming problem | Given an integer m x n matrix A and an integer m-vector b, we ask whether there is an integer n-vector x with elements in the set {0,1} such that Ax ≤ b.
(See page 1017)
|
|
|
|
| integer linear-programming problem | is like the 0-1 integer-programming problem except that the values of the vector x may be any integers rather than just 0 or 1.
(See page 1017)
|
|
|
|
| longest-simple-cycle problem | of determining a simple cycle (no repeated vertices) of maximum length in a graph.
(See page 1017)
|
|
|
|
| half 3-CNF satisfiability problem | given a 3-CNF formula φ with n variables and m clauses, where m is even. We wish to determine whether there exists a truth assignment to the variables of φ such that exactly half the clauses evaluate to 0 and exactly half the clauses evaluate to 1.
(See page 1018)
|
|
|
|
| independent set | of a graph G = (V, E) is a subset V′ ⊆ V of vertices such that each edge in E is incident on at most one vertex in V′.
(See page 1018)
|
|
|
|
| independent-set problem | find a maximum-size independent set in G.
(See page 1018)
|
|
|
|
| k-coloring | of an undirected graph G = (V, E) is a function c : V → {1,2,...,k} such that c(u) ≠ c(v) for every edge u, v) ∈ E. In other words, the numbers 1,2,...,k represent the k colors, and adjacent vertices must have different colors.
(See page 1019)
|
|
|
|
| graph-coloring problem | determine the minimum number of colors needed to color a given graph.
(See page 1019)
|
2002 McGraw-Hill Higher Education