Share This
table started by
pumpkin for the Computer Science Base
There is no user-contributed description yet.
Add More Topics
Save this view to a base, or just for yourself.
66 Computational problem topics matching:
Filter this Collection| x name | x image | x Complexity | x article |
|---|---|---|---|
| x Halting problem |
In computability theory, the halting problem can be stated as follows: Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever. This is equivalent to the problem of deciding,...
|
||
| x Post correspondence problem | NP-complete |
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.
The input of the...
|
|
| x Word problem for groups |
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element....
|
||
| x Word problem |
In computability theory, the word problem is a decision problem concerning formal languages. The problem is to construct an algorithm to decide for a given word if it belongs to a formal language or not.
Given a formal language L generated by a...
|
||
| x Wang tile |
|
Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems. They are modelled visually by equal-sized squares with a color on each edge which can be arranged side by side...
|
|
| x Kolmogorov complexity |
|
In algorithmic information theory (a subfield of computer science), the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object. It is named after Soviet Russian...
|
|
| x Hilbert's tenth problem |
Hilbert's tenth problem is the tenth on the list of Hilbert's problems of 1900. Its statement is as follows:
Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process...
|
||
| x Subset sum problem | NP-complete |
In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set of integers, is there a non-empty subset whose sum is zero? For example, given the set { −7, −3, −2, 5, 8},...
|
|
| x Partition problem | NP-complete |
In computer science, the partition problem is the task of deciding whether a given multiset of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. Although the...
|
|
| x Travelling salesman problem |
|
NP-complete |
The travelling salesman problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible...
|
| x 2-satisfiability |
In computer science, 2-satisfiability (abbreviated as 2-SAT or just 2SAT) is the problem of determining whether a collection of two-valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all the...
|
||
| x Boolean satisfiability problem | NP-complete |
In computer science, satisfiability (often written in all capitals or abbreviated SAT) is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE. Equally important...
|
|
| x Subgraph isomorphism problem | NP-complete |
In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H. Subgraph isomorphism is a...
|
|
| x Induced subgraph isomorphism problem |
In complexity theory and graph theory, induced subgraph isomorphism is an NP-complete decision problem that involves finding a given graph as an induced subgraph of a larger graph.
Formally, the problem takes as input two graphs G1=(V1, E1) and G2=...
|
||
| x Graph coloring | NP-complete |
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a...
|
|
| x Register allocation |
In compiler optimization, register allocation is the process of assigning a large number of target program variables onto a small number of CPU registers. Register allocation can happen over a basic block (local register allocation), over a whole...
|
||
| x Firing squad synchronization problem |
|
The firing squad synchronization problem is a problem in computer science and cellular automata in which the goal is to design a cellular automaton that, starting with a single active cell, eventually reaches a state in which all cells are...
|
|
| x 3SAT | NP-complete | ||
| x Vertex cover problem | NP-complete |
In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical optimization...
|
|
| x Dominating set problem | NP-complete |
The dominating set problem is an NP-complete problem in graph theory.
An instance of the dominating set problem consists of:
The problem is to determine whether there is a dominating set of size K or less for G. That is, we want to know if there is...
|
|
| x Domatic number | NP-complete |
In graph theory, a domatic partition of a graph G = (V,E) is a partition of V into disjoint sets V1, V2,...,VK such that each Vi is a dominating set for G. The figure on the right shows a domatic partition of a graph; here the dominating set V1...
|
|
| x Complete coloring | NP-complete |
In graph theory, complete coloring is the opposite of harmonious coloring in the sense that it is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the...
|
|
| x Monochromatic triangle | NP-complete |
The monochromatic triangle problem is a decision problem that is known to be NP-complete.
Input: An n-node undirected graph G(V,E) with node set V and edge set E.
Question: Can the edges, E, of G be partitioned into two disjoint sets E1 and E2, such...
|
|
| x Feedback vertex set | NP-complete |
In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph. The...
|
|
| x Feedback arc set | NP-complete |
In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG). One way to do this is simply to drop...
|
|
| x Clique | NP-complete |
In the mathematical area of graph theory, a clique (pronounced /ˈkliːk/ or /ˈklɪk/) in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of...
|
|
| x Independent set problem | NP-complete |
In mathematics, the independent set problem (Independent Set or IS) is a well-known problem in graph theory. The independent set problem is known to be NP-complete. It is closely related to the clique problem.
In a simple graph G, an independent set...
|
|
| x Induced path |
|
NP-complete |
In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge...
|
| x Maximum cut | NP-complete |
For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the max-cut problem.
The problem can be stated simply as follows. One wants a subset S of the vertex...
|
|
| x Hamiltonian completion | NP-complete |
The Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian.
The problem is clearly NP-hard in general case (since its solution gives an answer to the NP-complete problem of determining whether...
|
|
| x Hamiltonian path problem | NP-complete |
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both...
|
|
| x Graph homomorphism | NP-complete |
In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps adjacent vertices to adjacent vertices.
A graph homomorphism f from a graph G = (V,E) to a graph G'...
|
|
| x Metric dimension | NP-complete |
In graph theory, the metric dimension of a graph G is the minimum number of vertices in a subset S of G such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP...
|
|
| x Degree constrained spanning tree | NP-complete |
In graph theory, a degree-constrained spanning tree is a spanning tree where the maximum vertex degree is limited to a certain constant k. The degree-constrained spanning tree problem is to determine whether a particular graph has such a spanning...
|
|
| x Minimum degree spanning tree | NP-complete |
In graph theory, for a connected graph G, a spanning tree T is a subgraph of G with the least number of edges that still spans G. A number of properties can be proved about T. T is acyclic, has ( | V | − 1) edges where V is the number of vertices in...
|
|
| x Maximum leaf spanning tree | NP-complete |
Maximum Leaf Spanning Tree
Input: n-node undirected graph G(V,E); positive integer k
|
|
| x Steiner tree |
|
NP-complete |
The Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the...
|
| x Graph partition | NP-complete |
In mathematics, the graph partition problem is defined on data represented in the form of a graph G= (V,E), with V vertices and E edges, such that it is possible to partition G into smaller components with specific properties. For instance, a k-way...
|
|
| x Bottleneck traveling salesman problem | NP-complete |
The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. It is stated as follows: Find the Hamiltonian cycle in a weighted graph which minimizes the weight of the most weighty edge of the...
|
|
| x Longest path problem | NP-complete |
In the mathematical discipline of graph theory, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices. Unlike the shortest path problem,...
|
|
| x Vehicle routing problem |
|
NP-complete |
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. Proposed by Dantzig and Ramser in 1959, VRP is an important problem in the fields of...
|
| x Quadratic assignment problem | NP-complete |
The quadratic assignment problem (QAP) is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems.
The problem models the...
|
|
| x 3-dimensional matching | NP-complete |
In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (a.k.a. 2-dimensional matching) to 3-uniform hypergraphs. Finding a largest 3-dimensional matching is a well-known NP-hard problem in...
|
|
| x Exact cover | NP-complete |
In mathematics, given a collection of subsets of a set X, an exact cover is a subcollection of such that each element in X is contained in exactly one subset in . One says that each element in X is covered by exactly one subset in . An exact...
|
|
| x Set packing | NP-complete |
Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems.
Suppose we have a finite set S and a list of subsets of S. Then, the set packing problem asks if some...
|
|
| x Set splitting problem | NP-complete |
In computational complexity theory, the Set Splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are...
|
|
| x Set cover problem |
|
NP-complete |
The set covering problem (SCP) is a classical question in computer science and complexity theory. It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms. It was also one of...
|
| x Bipartite dimension | NP-complete |
In the mathematical field of graph theory, the bipartite dimension of a graph G = (V, E) is the minimum number of bicliques, that is, complete bipartite subgraphs, needed to cover all edges in E. A collection of bicliques covering all edges in G is...
|
|
| x Hitting set | NP-complete |
The hitting set problem is an NP-complete problem in set theory. For a given list of sets, a hitting set is a set of elements so that each set in the given list is 'touched' by the hitting set. In the hitting set problem, the task is to find a small...
|
|
| x 3-partition problem | NP-complete |
The 3-partition problem is an NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. More precisely, given a multiset S of n = 3 m positive...
|
|
| x Bin packing problem | NP-complete |
In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used.
There are...
|
|
| x Shortest common supersequence | NP-complete |
In computer science, the shortest common supersequence problem is a problem closely related to the longest common subsequence problem. Given two sequences X = and Y = , a sequence U = is a common...
|
|
| x Longest common subsequence problem | NP-complete |
The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). Note that subsequence is different from a substring, see substring vs. subsequence. It is a classic...
|
|
| x Boolean conjunctive query | NP-complete |
In the theory of relational databases, a Boolean conjunctive query is a conjunctive query without distinguished predicates, i.e., a query in the form , where each Ri is a relation symbol and each ti is a tuple of variables and constants; the number...
|
|
| x Serializability | NP-complete |
In concurrency control of databases, transaction processing (transaction management), and various transactional applications (e.g., transactional memory and software transactional memory), both centralized and distributed, a transaction schedule is...
|
|
| x Multiprocessor scheduling | NP-complete |
In computer science, multiprocessor scheduling is an NP-hard optimization problem. The problem statement is: "Given a set J of jobs where job ji has length li and a number of processors mi, what is the minimum possible time required to schedule all...
|
|
| x Flow Shop Scheduling Problem | NP-complete |
Flow Shop Scheduling Problems, or FSPs, are a class of scheduling problems with a work shop or group shop in which the flow control shall enable an appropriate sequencing for each job and for processing on a set of machines or with other resources 1...
|
|
| x Linear programming |
|
NP-complete |
Linear programming (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear...
|
| x Knapsack problem | NP-complete |
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to...
|
|
| x Generalized Assignment Problem | NP-complete |
In applied mathematics, the maximum generalized assignment problem is a problem in combinatorial optimization. This problem is a generalization of the assignment problem in which both tasks and agents have a size. Moreover, the size of each task...
|
|
