|
Kronecker Coefficient
In mathematics, Kronecker coefficients ''g''λ''μν'' describe the decomposition of the tensor product (= Kronecker product) of two irreducible representations of a symmetric group into irreducible representations. They play an important role algebraic combinatorics and geometric complexity theory. They were introduced by Murnaghan in 1938. Definition Given a partition λ of ''n'', write ''V''λ for the Specht module associated to λ. Then the Kronecker coefficients ''g''λ''μν'' are given by the rule : V_\mu \otimes V_\nu = \bigoplus_\lambda g_^ V_\lambda. One can interpret this on the level of symmetric functions, giving a formula for the Kronecker product of two Schur polynomials: :s_\mu \star s_\nu = \sum_ g_^ s_\lambda. This is to be compared with Littlewood–Richardson coefficients, where one instead considers the induced representation : \uparrow_^ \left ( V_\mu \otimes V_\nu \right ) = \bigoplus_\lambda c_^ V_\lambda, and the corresponding operation of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tensor Product
In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otimes W denoted v \otimes w. An element of the form v \otimes w is called the tensor product of and . An element of V \otimes W is a tensor, and the tensor product of two vectors is sometimes called an ''elementary tensor'' or a ''decomposable tensor''. The elementary tensors span V \otimes W in the sense that every element of V \otimes W is a sum of elementary tensors. If bases are given for and , a basis of V \otimes W is formed by all tensor products of a basis element of and a basis element of . The tensor product of two vector spaces captures the properties of all bilinear maps in the sense that a bilinear map from V\times W into another vector space factors uniquely through a linear map V\otimes W\to Z (see Universal property). Tenso ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
♯P
In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute ''f''(''x'')", where ''f'' is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P-complete. Relation to decision problems An NP decision problem is often of the form "Are there any solutions that satisfy certain constraints?" For example: * Are there any subsets of a list of integers that add up to zero? (subset sum problem) * Are there any Hamiltonian cycles in a given graph with cost less than 100? (traveling salesman problem) * Are there any variable assignments that satisfy a g ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algebraic Combinatorics
Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra. History The term "algebraic combinatorics" was introduced in the late 1970s. Through the early or mid-1990s, typical combinatorial objects of interest in algebraic combinatorics either admitted a lot of symmetries (association schemes, strongly regular graphs, posets with a group action) or possessed a rich algebraic structure, frequently of representation theoretic origin (symmetric functions, Young tableaux). This period is reflected in the area 05E, ''Algebraic combinatorics'', of the AMS Mathematics Subject Classification, introduced in 1991. Scope Algebraic combinatorics has come to be seen more expansively as an area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Partition (number Theory)
In number theory and combinatorics, a partition of a positive integer , also called an integer partition, is a way of writing as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. (If order matters, the sum becomes a composition.) For example, can be partitioned in five distinct ways: : : : : : The order-dependent composition is the same partition as , and the two distinct compositions and represent the same partition as . A summand in a partition is also called a part. The number of partitions of is given by the partition function . So . The notation means that is a partition of . Partitions can be graphically visualized with Young diagrams or Ferrers diagrams. They occur in a number of branches of mathematics and physics, including the study of symmetric polynomials and of the symmetric group and in group representation theory in general. Examples The seven partitions of 5 are: * 5 * 4 + 1 * 3 + ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Character Theory
In mathematics, more specifically in group theory, the character of a group representation is a function on the group that associates to each group element the trace of the corresponding matrix. The character carries the essential information about the representation in a more condensed form. Georg Frobenius initially developed representation theory of finite groups entirely based on the characters, and without any explicit matrix realization of representations themselves. This is possible because a complex representation of a finite group is determined (up to isomorphism) by its character. The situation with representations over a field of positive characteristic, so-called "modular representations", is more delicate, but Richard Brauer developed a powerful theory of characters in this case as well. Many deep theorems on the structure of finite groups use characters of modular representations. Applications Characters of irreducible representations encode many important propert ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
♯P-complete
The #P-complete problems (pronounced "sharp P complete" or "number P complete") form a complexity class in computational complexity theory. The problems in this complexity class are defined by having the following two properties: *The problem is in #P, the class of problems that can be defined as counting the number of accepting paths of a polynomial-time non-deterministic Turing machine. *The problem is #P-hard, meaning that every other problem in #P has a Turing reduction or polynomial-time counting reduction to it. A counting reduction is a pair of polynomial-time transformations from inputs of the other problem to inputs of the given problem and from outputs of the given problem to outputs of the other problem, allowing the other problem to be solved using any subroutine for the given problem. A Turing reduction is an algorithm for the other problem that makes a polynomial number of calls to a subroutine for the given problem and, outside of those calls, uses polynomial tim ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Geometric Complexity Theory
Geometric complexity theory (GCT), is a research program in computational complexity theory proposed by Ketan Mulmuley and Milind Sohoni. The goal of the program is to answer the most famous open problem in computer science – whether P = NP – by showing that the complexity class P is not equal to the complexity class NP. The idea behind the approach is to adopt and develop advanced tools in algebraic geometry and representation theory (i.e., geometric invariant theory) to prove lower bounds for problems. Currently the main focus of the program is on algebraic complexity classes. Proving that computing the permanent cannot be efficiently reduced to computing determinants is considered to be a major milestone for the program. These computational problems can be characterized by their symmetries. The program aims at utilizing these symmetries for proving lower bounds. The approach is considered by some to be the only viable currently active program to separate P fro ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-hardness
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem. A more precise specification is: a problem ''H'' is NP-hard when every problem ''L'' in NP can be reduced in polynomial time to ''H''; that is, assuming a solution for ''H'' takes 1 unit time, ''H''s solution can be used to solve ''L'' in polynomial time. As a consequence, finding a polynomial time algorithm to solve any NP-hard problem would give polynomial time algorithms for all the problems in NP. As it is suspected that P≠NP, it is unlikely that such an algorithm exists. It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven. Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class. Defi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
GapP
GapP is a counting complexity class, consisting of all of the functions ''f'' such that there exists a polynomial-time non-deterministic Turing machine ''M'' where, for any input ''x'', ''f(x)'' is equal to the number of accepting paths of ''M'' minus the number of rejecting paths of ''M''. GapP is exactly the closure of #P under subtraction. It also has all the other closure properties of #P, such as addition, multiplication, and binomial coefficients. The counting class AWPP is defined in terms of GapP functions. References * S. Fenner, L. Fortnow, and S. KurtzGap-definable counting classes ''Journal of Computer and System Sciences'' 48(1):116-148, 1994. * {{Comp-sci-theory-stub Complexity classes ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kronecker Product
In mathematics, the Kronecker product, sometimes denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It is a generalization of the outer product (which is denoted by the same symbol) from vectors to matrices, and gives the matrix of the tensor product linear map with respect to a standard choice of basis. The Kronecker product is to be distinguished from the usual matrix multiplication, which is an entirely different operation. The Kronecker product is also sometimes called matrix direct product. The Kronecker product is named after the German mathematician Leopold Kronecker (1823–1891), even though there is little evidence that he was the first to define and use it. The Kronecker product has also been called the ''Zehfuss matrix'', and the ''Zehfuss product'', after , who in 1858 described this matrix operation, but Kronecker product is currently the most widely used. Definition If A is an matrix and B is a matrix, then the Kr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Schur Polynomial
In mathematics, Schur polynomials, named after Issai Schur, are certain symmetric polynomials in ''n'' variables, indexed by partitions, that generalize the elementary symmetric polynomials and the complete homogeneous symmetric polynomials. In representation theory they are the characters of polynomial irreducible representations of the general linear groups. The Schur polynomials form a linear basis for the space of all symmetric polynomials. Any product of Schur polynomials can be written as a linear combination of Schur polynomials with non-negative integral coefficients; the values of these coefficients is given combinatorially by the Littlewood–Richardson rule. More generally, skew Schur polynomials are associated with pairs of partitions and have similar properties to Schur polynomials. Definition (Jacobi's bialternant formula) Schur polynomials are indexed by integer partitions. Given a partition , where , and each is a non-negative integer, the functions a_ (x_1, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
