|
Reconfiguration
In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces. Types of problems Here, a state space is a discrete set of configurations of a system or solutions of a combinatorial problem, called states, together with a set of allowed moves linking one state to another. Reconfiguration problems may ask: *For a given class of problems, is the state space always connected? That is, can one transform every pair of states into each other with a sequence of moves? If not, what is the computational complexity of determining whether the state space for a particular problem is connected? *What is the diameter of the state space, the smallest number such that every two states can be transformed into each other with at most moves? *Given two states, what is the complexity of determining whether they can be transformed into each other, or of finding the shortest sequence of moves for tran ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Token Reconfiguration
In computational complexity theory and combinatorics, the token reconfiguration problem is a reconfiguration problem on a graph with both an initial and desired state for tokens. Given a graph G, an initial state of tokens is defined by a subset V \subset V(G) of the vertices of the graph; let n = , V, . Moving a token from vertex v_1 to vertex v_2 is valid if v_1 and v_2 are joined by a path in G that does not contain any other tokens; note that the distance traveled within the graph is inconsequential, and moving a token across multiple edges sequentially is considered a single move. A desired end state is defined as another subset V' \subset V(G). The goal is to minimize the number of valid moves to reach the end state from the initial state. Motivation The problem is motivated by so-called sliding puzzles, which are in fact a variant of this problem, often restricted to rectangular grid graphs with no holes. The most famous such puzzle, the 15 puzzle, is a variant of this ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nondeterministic Constraint Logic
In theoretical computer science, nondeterministic constraint logic is a combinatorial system in which an orientation is given to the edges of a weighted undirected graph, subject to certain constraints. One can change this orientation by steps in which a single edge is reversed, subject to the same constraints. The constraint logic problem and its variants have been proven to be PSPACE-complete to determine whether there exists a sequence of moves that reverses a specified edge and are very useful to show various games and puzzles are PSPACE-hard or PSPACE-complete. This is a form of reversible logic in that each sequence of edge orientation changes can be undone. The hardness of this problem has been used to prove that many games and puzzles have high game complexity. Constraint graphs In the simplest version of nondeterministic constraint logic, each edge of an undirected graph has weight either one or two. (The weights may also be represented graphically by drawing edges of w ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cereceda's Conjecture
In the mathematics of graph coloring, Cereceda’s conjecture is an unsolved problem on the distance between pairs of colorings of sparse graphs. It states that, for two different colorings of a graph of degeneracy , both using at most colors, it should be possible to reconfigure one coloring into the other by changing the color of one vertex at a time, using a number of steps that is quadratic in the size of the graph. The conjecture is named after Luis Cereceda, who formulated it in his 2007 doctoral dissertation. Background The degeneracy of an undirected graph is the smallest number such that every non-empty subgraph of has at least one vertex of degree at most . If one repeatedly removes a minimum-degree vertex from until no vertices are left, then the largest of the degrees of the vertices at the time of their removal will be exactly , and this method of repeated removal can be used to compute the degeneracy of any graph in linear time. Greedy coloring the vertices in t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rotation Distance
In discrete mathematics and theoretical computer science, the rotation distance between two binary trees with the same number of nodes is the minimum number of tree rotations needed to reconfigure one tree into another. Because of a combinatorial equivalence between binary trees and triangulations of convex polygons, rotation distance is equivalent to the flip distance for triangulations of convex polygons. Rotation distance was first defined by Karel Čulík II and Derick Wood in 1982. Every two -node binary trees have rotation distance at most , and some pairs of trees have exactly this distance. The computational complexity of computing the rotation distance is unknown. Definition A binary tree is a structure consisting of a set of nodes, one of which is designated as the root node, in which each remaining node is either the ''left child'' or ''right child'' of some other node, its ''parent'', and in which following the parent links from any node eventually leads to the root ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
PSPACE-complete
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE. Problems known to be PSPACE-complete include determining properties of regular expressions and context-sensitive grammars, determining the truth of quantified Boolean formulas, step-by-step changes between solutions of combinatorial optimization problems, and many puzzles and games. Theory A problem is defined to be PSPACE-complete if it can be solved using a polynomial amount of memory (it belongs to PSPACE) and every problem in PSPACE can be tr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
State Space
A state space is the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory. For instance, the toy problem Vacuum World has a discrete finite state space in which there are a limited set of configurations that the vacuum and dirt can be in. A "counter" system, where states are the natural numbers starting at 1 and are incremented over time has an infinite discrete state space. The angular position of an undamped pendulum is a continuous (and therefore infinite) state space. Definition In the theory of dynamical systems, the state space of a discrete system defined by a function ''ƒ'' can be modeled as a directed graph where each possible state of the dynamical system is represented by a vertex with a directed edge from ''a'' to ''b'' if and only if ''ƒ''(''a'') = ''b''. This is known as a state diagram. For a cont ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Reconfigurability
{{Refimprove, date=May 2008 Reconfigurability denotes the Reconfigurable Computing capability of a system, so that its behavior can be changed by reconfiguration, i. e. by loading different configware code. This static reconfigurability distinguishes between reconfiguration time and run time. Dynamic reconfigurability denotes the capability of a dynamically reconfigurable system that can dynamically change its behavior during run time, usually in response to dynamic changes in its environment. In the context of wireless communication dynamic reconfigurability tackles the changeable behavior of wireless networks and associated equipment, specifically in the fields of radio spectrum, radio access technologies, protocol stacks, and application services. Research regarding the (dynamic) reconfigurability of wireless communication systems is ongoing for example in working group 6 of the Wireless World Research Forum (WWRF), in the Wireless Innovation Forum (WINNF) (formerly Software Defi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Co-NP-complete
In Computational complexity theory, complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial overhead. If P (complexity), P is different from co-NP, then all of the co-NP-complete problems are not solvable in polynomial time. If there exists a way to solve a co-NP-complete problem quickly, then that algorithm can be used to solve all co-NP problems quickly. Each co-NP-complete problem is the complement (complexity), complement of an NP-complete problem. There are some problems in both NP (complexity), NP and co-NP, for example all problems in P (complexity), P or integer factorization. However, it is not known if the sets are equal, although inequality is thought more likely. See co-NP and NP-complete for more details. Fortune showed in 1979 that if any sparse language is co-NP-complete (or even j ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Degeneracy (graph Theory)
In graph theory, a ''k''-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most ''k'': that is, some vertex in the subgraph touches ''k'' or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of ''k'' for which it is ''k''-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph. Degeneracy is also known as the ''k''-core number, width, and linkage, and is essentially the same as the coloring number or Szekeres–Wilf number (named after ). ''k''-degenerate graphs have also been called ''k''-inductive graphs. The degeneracy of a graph may be computed in linear time by an algorithm that repeatedly removes minimum-degree vertices. The connected components that are left after all vertices of degree less than ''k'' have been (repeatedly) removed are called the ''k''-cores of the graph and the degeneracy of a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kempe Chain
Kempe may refer to: * Kempe baronets, a title in the Baronetage of England * Kempe chain, part of the four-colour theorem * Kempe Fjord, King Christian X Land, Greenland * Kempe Glacier, Antarctica * Kempe Hill, former name of Camp Hill, West Midlands, England People with the surname * Alfred Kempe (1849–1922), English mathematician * Arnold E. Kempe (born 1927), American lawyer and politician * Carl Kempe (1884–1967), Swedish paper producer * Charles Eamer Kempe (1837–1907), English stained glass designer * C. Henry Kempe (1922–1984), American pediatrician who identified the Battered child syndrome * Kempe Gowda I (1513–69), Yelahanka chieftain, founded the city of Bangalore * Margery Kempe (c. 1373–after 1438), English autobiographer, religious pilgrim * Raymond J. Kempe (born 1931), American lawyer and politician * Rudolf Kempe (1910–76), German conductor * William Kempe (died c. 1603), English actor and morris dancer See also * Kemp ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Coloring
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 graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. Vertex coloring is often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as-is. This is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial Time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expresse ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
