42 relations: Algorithm, Backtracking, Binary relation, Bipartite graph, Computer science, Computers and Intractability, Constraint satisfaction problem, Converse relation, Cover (topology), Dancing Links, Decision problem, Depth-first search, Difference-map algorithm, Disjoint sets, Donald Knuth, Doubly linked list, Eight queens puzzle, Empty set, Function (mathematics), Heterogeneous relation, Hypergraph, Incidence matrix, Intersection (set theory), Karp's 21 NP-complete problems, Knuth's Algorithm X, List of NP-complete problems, Matching (graph theory), Mathematics, Nondeterministic algorithm, NP-completeness, Partition of a set, Pentomino, Recursion (computer science), Reduction (complexity), Restriction (mathematics), Set cover problem, Subset, Sudoku, Sudoku solving algorithms, Surjective function, Union (set theory), 3-dimensional matching.
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.
In mathematics, a binary relation on a set A is a set of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2.
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph.
Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.
In computer science, more specifically computational complexity theory, Computers and Intractability: A Guide to the Theory of NP-Completeness is an influential textbook by Michael Garey and David S. Johnson.
Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations.
In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation.
In mathematics, a cover of a set X is a collection of sets whose union contains X as a subset.
In computer science, dancing links is the technique suggested by Donald Knuth to efficiently implement his Algorithm X. Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem.
In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.
The difference-map algorithm is a search algorithm for general constraint satisfaction problems.
In mathematics, two sets are said to be disjoint sets if they have no element in common.
Donald Ervin Knuth (born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University.
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes.
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other.
In mathematics, and more specifically set theory, the empty set or null set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero.
In mathematics, a function was originally the idealization of how a varying quantity depends on another quantity.
In mathematics, a heterogeneous relation is a subset of a Cartesian product A × B, where A and B are distinct sets.
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices.
In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects.
In mathematics, the intersection A ∩ B of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements.
In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete.
"Algorithm X" is the name Donald Knuth used in his paper "Dancing Links" to refer to "the most obvious trial-and-error approach" for finding all solutions to the exact cover problem.
This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems.
In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices.
Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.
In computer science, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm.
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
In mathematics, a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets.
A pentomino (or 5-omino) is a polyomino of order 5, that is, a polygon in the plane made of 5 equal-sized squares connected edge-to-edge.
Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem (as opposed to iteration).
In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem.
In mathematics, the restriction of a function f is a new function f\vert_A obtained by choosing a smaller domain A for the original function f. The notation f is also used.
The set cover problem is a classical question in combinatorics, computer science and complexity theory.
In mathematics, a set A is a subset of a set B, or equivalently B is a superset of A, if A is "contained" inside B, that is, all elements of A are also elements of B. A and B may coincide.
(originally called Number Place) is a logic-based, combinatorial number-placement puzzle.
A standard Sudoku contains 81 cells, in a 9×9 grid, and has 9 boxes, each box being the intersection of the first, middle, or last 3 rows, and the first, middle, or last 3 columns.
In mathematics, a function f from a set X to a set Y is surjective (or onto), or a surjection, if for every element y in the codomain Y of f there is at least one element x in the domain X of f such that f(x).
In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection.
In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (also known as 2-dimensional matching) to 3-uniform hypergraphs.