Misplaced Pages

#171828

43-501: EXPTIME is one intuitive class in an exponential hierarchy of complexity classes with increasingly more complex oracles or quantifier alternations. For example, the class 2-EXPTIME is defined similarly to EXPTIME but with a doubly exponential time bound. This can be generalized to higher and higher time bounds. EXPTIME can also be reformulated as the space class APSPACE, the set of all problems that can be solved by an alternating Turing machine in polynomial space. EXPTIME relates to

86-490: A Σ k − 1 P {\displaystyle \Sigma _{k-1}^{\mathsf {P}}} oracle ) and Σ 0 E = E {\displaystyle \Sigma _{0}^{\mathsf {E}}={\mathsf {E}}} . One also defines An equivalent definition is that a language L is in Σ k E {\displaystyle \Sigma _{k}^{\mathsf {E}}} if and only if it can be written in

129-629: A Σ k − 1 P {\displaystyle \Sigma _{k-1}^{\mathsf {P}}} oracle), Σ 0 E X P = E X P {\displaystyle \Sigma _{0}^{\mathsf {EXP}}={\mathsf {EXP}}} , and again: A language L is in Σ k E X P {\displaystyle \Sigma _{k}^{\mathsf {EXP}}} if and only if it can be written as where R ( x , y 1 , … , y k ) {\displaystyle R(x,y_{1},\ldots ,y_{k})}

172-407: A Base64 representation. Besides avoiding wasted space, this compactness encourages locality of reference . However, for a large sparse graph , adjacency lists require less storage space, because they do not waste any space representing edges that are not present. An alternative form of adjacency matrix (which, however, requires a larger amount of space) replaces the numbers in each element of

215-423: A permutation matrix P such that In particular, A 1 and A 2 are similar and therefore have the same minimal polynomial , characteristic polynomial , eigenvalues , determinant and trace . These can therefore serve as isomorphism invariants of graphs. However, two graphs may possess the same set of eigenvalues but not be isomorphic. Such linear operators are said to be isospectral . If A

258-537: A directed graph, or (by using a packed triangular format and only storing the lower triangular part of the matrix) approximately | V  |  / 16 bytes to represent an undirected graph. Although slightly more succinct representations are possible, this method gets close to the information-theoretic lower bound for the minimum number of bits needed to represent all n -vertex graphs. For storing graphs in text files , fewer bits per byte can be used to ensure that all bytes are text characters, for instance by using

301-464: A graph and the eigenvalues and eigenvectors of its adjacency matrix is studied in spectral graph theory . The adjacency matrix of a graph should be distinguished from its incidence matrix , a different matrix representation whose elements indicate whether vertex–edge pairs are incident or not, and its degree matrix , which contains information about the degree of each vertex. For a simple graph with vertex set U = { u 1 , …, u n } ,

344-419: A number of moves that is polynomial in the size of the board are often PSPACE-complete . The same is true of exponentially long games in which non-repetition is automatic. Another set of important EXPTIME-complete problems relates to succinct circuits . Succinct circuits are simple machines used to describe some graphs in exponentially less space. They accept two vertex numbers as input and output whether there

387-405: A vertex is given by the corresponding row sum and the out-degree is given by the corresponding column sum. Directed Cayley graph of S 4 Coordinates are 0–23. As the graph is directed, the matrix is not necessarily symmetric . The adjacency matrix of a complete graph contains all ones except along the diagonal where there are only zeros. The adjacency matrix of an empty graph

430-414: Is a square matrix used to represent a finite graph . The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple graph , the adjacency matrix is a (0,1)-matrix with zeros on its diagonal. If the graph is undirected (i.e. all of its edges are bidirectional), the adjacency matrix is symmetric . The relationship between

473-623: Is a zero matrix . The adjacency matrix of an undirected simple graph is symmetric , and therefore has a complete set of real eigenvalues and an orthogonal eigenvector basis. The set of eigenvalues of a graph is the spectrum of the graph. It is common to denote the eigenvalues by λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n . {\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}.} The greatest eigenvalue λ 1 {\displaystyle \lambda _{1}}

SECTION 10

#1732851133172

516-444: Is a bipartite multigraph or weighted graph , then the elements b i,j are taken to be the number of edges between the vertices or the weight of the edge ( u i , v j ) , respectively. An ( a , b , c ) -adjacency matrix A of a simple graph has A i , j = a if ( i , j ) is an edge, b if it is not, and c on the diagonal. The Seidel adjacency matrix is a (−1, 1, 0) -adjacency matrix. This matrix

559-452: Is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. Problems that are EXPTIME-complete might be thought of as the hardest problems in EXPTIME. Notice that although it is unknown whether NP is equal to P, we do know that EXPTIME-complete problems are not in P; it has been proven that these problems cannot be solved in polynomial time , by

602-728: Is also an eigenvalue of A if G is a bipartite graph . In particular − d is an eigenvalue of any d -regular bipartite graph. The difference λ 1 − λ 2 {\displaystyle \lambda _{1}-\lambda _{2}} is called the spectral gap and it is related to the expansion of G . It is also useful to introduce the spectral radius of A {\displaystyle A} denoted by λ ( G ) = max | λ i | < d | λ i | {\displaystyle \lambda (G)=\max _{\left|\lambda _{i}\right|<d}|\lambda _{i}|} . This number

645-457: Is an edge between them. For many natural P-complete graph problems, where the graph is expressed in a natural representation such as an adjacency matrix , solving the same problem on a succinct circuit representation is EXPTIME-complete, because the input is exponentially smaller; but this requires nontrivial proof, since succinct circuits can only describe a subclass of graphs. Exponential hierarchy In computational complexity theory ,

688-607: Is bounded above by the maximum degree. This can be seen as result of the Perron–Frobenius theorem , but it can be proved easily. Let v be one eigenvector associated to λ 1 {\displaystyle \lambda _{1}} and x the entry in which v has maximum absolute value. Without loss of generality assume v x is positive since otherwise you simply take the eigenvector - v , also associated to λ 1 {\displaystyle \lambda _{1}} . Then For d -regular graphs, d

731-538: Is bounded by λ ( G ) ≥ 2 d − 1 − o ( 1 ) {\displaystyle \lambda (G)\geq 2{\sqrt {d-1}}-o(1)} . This bound is tight in the Ramanujan graphs , which have applications in many areas. Suppose two directed or undirected graphs G 1 and G 2 with adjacency matrices A 1 and A 2 are given. G 1 and G 2 are isomorphic if and only if there exists

774-525: Is computable in time 2 | x | c {\displaystyle 2^{|x|^{c}}} for some c , which again implicitly bounds the length of y i . Equivalently, EXPH is the class of languages computable in time 2 n c {\displaystyle 2^{n^{c}}} on an alternating Turing machine with constantly many alternations. Complexity Zoo : Class EH Adjacency matrix In graph theory and computer science , an adjacency matrix

817-415: Is more common in other applied sciences (e.g., dynamical systems, physics, network science) where A is sometimes used to describe linear dynamics on graphs. Using the first definition, the in-degrees of a vertex can be computed by summing the entries of the corresponding column and the out-degree of vertex by summing the entries of the corresponding row. When using the second definition, the in-degree of

860-453: Is positive, then n is the distance between vertex i and vertex j . A great example of how this is useful is in counting the number of triangles in an undirected graph G , which is exactly the trace of A divided by 3 or 6 depending on whether the graph is directed or not. We divide by those values to compensate for the overcounting of each triangle. In an undirected graph, each triangle will be counted twice for all three nodes, because

903-426: Is the adjacency list . The space needed to represent an adjacency matrix and the time needed to perform operations on them is dependent on the matrix representation chosen for the underlying matrix. Sparse matrix representations only store non-zero matrix entries and implicitly represent the zero entries. They can, for example, be used to represent sparse graphs without incurring the space overhead from storing

SECTION 20

#1732851133172

946-402: Is the adjacency matrix of the directed or undirected graph G , then the matrix A (i.e., the matrix product of n copies of A ) has an interesting interpretation: the element ( i , j ) gives the number of (directed or undirected) walks of length n from vertex i to vertex j . If n is the smallest nonnegative integer, such that for some i , j , the element ( i , j ) of A

989-700: Is the first eigenvalue of A for the vector v = (1, …, 1) (it is easy to check that it is an eigenvalue and it is the maximum because of the above bound). The multiplicity of this eigenvalue is the number of connected components of G , in particular λ 1 > λ 2 {\displaystyle \lambda _{1}>\lambda _{2}} for connected graphs. It can be shown that for each eigenvalue λ i {\displaystyle \lambda _{i}} , its opposite − λ i = λ n + 1 − i {\displaystyle -\lambda _{i}=\lambda _{n+1-i}}

1032-565: Is the union of the classes Σ k E X P {\displaystyle \Sigma _{k}^{\mathsf {EXP}}} , where Σ k E X P = N E X P Σ k − 1 P {\displaystyle \Sigma _{k}^{\mathsf {EXP}}={\mathsf {NEXP}}^{\Sigma _{k-1}^{\mathsf {P}}}} (languages computable in nondeterministic time 2 n c {\displaystyle 2^{n^{c}}} for some constant c with

1075-488: Is used in studying strongly regular graphs and two-graphs . The distance matrix has in position ( i , j ) the distance between vertices v i and v j . The distance is the length of a shortest path connecting the vertices. Unless lengths of edges are explicitly provided, the length of a path is the number of edges in it. The distance matrix resembles a high power of the adjacency matrix, but instead of telling only whether or not two vertices are connected (i.e.,

1118-472: The exponential hierarchy is a hierarchy of complexity classes that is an exponential time analogue of the polynomial hierarchy . As elsewhere in complexity theory, “exponential” is used in two different meanings (linear exponential bounds 2 c n {\displaystyle 2^{cn}} for a constant c , and full exponential bounds 2 n c {\displaystyle 2^{n^{c}}} ), leading to two versions of

1161-406: The time hierarchy theorem . In computability theory , one of the basic undecidable problems is the halting problem : deciding whether a deterministic Turing machine (DTM) halts. One of the most fundamental EXPTIME-complete problems is a simpler version of this, which asks if a DTM halts on a given input in at most k steps. It is in EXPTIME because a trivial simulation requires O( k ) time, and

1204-585: The above expressions, the symbol ⊆ means "is a subset of", and the symbol ⊊ means "is a strict subset of". so at least one of the first three inclusions and at least one of the last three inclusions must be proper, but it is not known which ones are. It is also known that if P = NP , then EXPTIME = NEXPTIME , the class of problems solvable in exponential time by a nondeterministic Turing machine . More precisely, E ≠ NE if and only if there exist sparse languages in NP that are not in P . EXPTIME can be reformulated as

1247-403: The adjacency matrix is a square n  ×  n matrix A such that its element A ij is one when there is an edge from vertex u i to vertex u j , and zero when there is no edge. The diagonal elements of the matrix are all zero, since edges from a vertex to itself ( loops ) are not allowed in simple graphs. It is also sometimes useful in algebraic graph theory to replace

1290-403: The connection matrix, which contains Boolean values ), it gives the exact distance between them. The convention followed here (for undirected graphs) is that each edge adds 1 to the appropriate cell in the matrix, and each loop (an edge from a vertex to itself) adds 2 to the appropriate cell on the diagonal in the matrix. This allows the degree of a vertex to be easily found by taking the sum of

1333-738: The exponential hierarchy. This hierarchy is sometimes also referred to as the weak exponential hierarchy, to differentiate it from the strong exponential hierarchy. The complexity class EH is the union of the classes Σ k E {\displaystyle \Sigma _{k}^{\mathsf {E}}} for all k , where Σ k E = N E Σ k − 1 P {\displaystyle \Sigma _{k}^{\mathsf {E}}={\mathsf {NE}}^{\Sigma _{k-1}^{\mathsf {P}}}} (i.e., languages computable in nondeterministic time 2 c n {\displaystyle 2^{cn}} for some constant c with

EXPTIME - Misplaced Pages Continue

1376-563: The form where R ( x , y 1 , … , y n ) {\displaystyle R(x,y_{1},\ldots ,y_{n})} is a predicate computable in time 2 c | x | {\displaystyle 2^{c|x|}} (which implicitly bounds the length of y i ). Also equivalently, EH is the class of languages computable on an alternating Turing machine in time 2 c n {\displaystyle 2^{cn}} for some c with constantly many alternations. EXPH

1419-406: The input k is encoded using O(log k ) bits which causes exponential number of simulations. It is EXPTIME-complete because, roughly speaking, we can use it to determine if a machine solving an EXPTIME problem accepts in an exponential number of steps; it will not use more. The same problem with the number of steps written in unary is P-complete . Other examples of EXPTIME-complete problems include

1462-412: The latter convention of counting loops twice, whereas directed graphs typically use the former convention. The adjacency matrix A of a bipartite graph whose two parts have r and s vertices can be written in the form where B is an r  ×  s matrix, and 0 r , r and 0 s , s represent the r  ×  r and s  ×  s zero matrices . In this case,

1505-422: The many zero entries in the adjacency matrix of the sparse graph. In the following section the adjacency matrix is assumed to be represented by an array data structure so that zero and non-zero entries are all directly represented in storage. Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only | V  |  / 8 bytes to represent

1548-434: The matrix with pointers to edge objects (when edges are present) or null pointers (when there is no edge). It is also possible to store edge weights directly in the elements of an adjacency matrix. Besides the space tradeoff, the different data structures also facilitate different operations. Finding all vertices adjacent to a given vertex in an adjacency list is as simple as reading the list, and takes time proportional to

1591-426: The nonzero elements with algebraic variables. The same concept can be extended to multigraphs and graphs with loops by storing the number of edges between each two vertices in the corresponding matrix element, and by allowing nonzero diagonal elements. Loops may be counted either once (as a single edge) or twice (as two vertex-edge incidences), as long as a consistent convention is followed. Undirected graphs often use

1634-408: The other basic time and space complexity classes in the following way: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE . Furthermore, by the time hierarchy theorem and the space hierarchy theorem , it is known that P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE. In terms of DTIME , It is known that and also, by the time hierarchy theorem and the space hierarchy theorem , that In

1677-531: The path can be followed clockwise or counterclockwise : ijk or ikj. The adjacency matrix can be used to determine whether or not the graph is connected . If a directed graph has a nilpotent adjacency matrix (i.e., if there exists n such that A is the zero matrix), then it is a directed acyclic graph . The adjacency matrix may be used as a data structure for the representation of graphs in computer programs for manipulating graphs. The main alternative data structure, also in use for this application,

1720-660: The problem of evaluating a position in generalized chess , checkers , or Go (with Japanese ko rules). These games have a chance of being EXPTIME-complete because games can last for a number of moves that is exponential in the size of the board. In the Go example, the Japanese ko rule is known to imply EXPTIME-completeness, but it is not known if the American or Chinese rules for the game are EXPTIME-complete (they could range from PSPACE to EXPSPACE). By contrast, generalized games that can last for

1763-485: The smaller matrix B uniquely represents the graph, and the remaining parts of A can be discarded as redundant. B is sometimes called the biadjacency matrix . Formally, let G = ( U , V , E ) be a bipartite graph with parts U = { u 1 , ..., u r } , V = { v 1 , ..., v s } and edges E . The biadjacency matrix is the r  ×  s 0–1 matrix B in which b i , j = 1 if and only if ( u i , v j ) ∈ E . If G

EXPTIME - Misplaced Pages Continue

1806-432: The space class APSPACE, the set of all problems that can be solved by an alternating Turing machine in polynomial space. This is one way to see that PSPACE ⊆ EXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine. A decision problem is EXPTIME-complete if it is in EXPTIME and every problem in EXPTIME has a polynomial-time many-one reduction to it. In other words, there

1849-491: The values in either its respective row or column in the adjacency matrix. Coordinates are 1–6. Nauru graph Coordinates are 0–23. White fields are zeros, colored fields are ones. The adjacency matrix of a directed graph can be asymmetric. One can define the adjacency matrix of a directed graph either such that The former definition is commonly used in graph theory and social network analysis (e.g., sociology, political science, economics, psychology). The latter

#171828