Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Computational Complexity of Plethysm Coefficients
112
0
0.0
(
0
)
Added by
Nick Fischer
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In two papers, Burgisser and Ikenmeyer (STOC 2011, STOC 2013) used an adaption of the geometric complexity theory (GCT) approach by Mulmuley and Sohoni (Siam J Comput 2001, 2008) to prove lower bounds on the border rank of the matrix multiplication tensor. A key ingredient was information about certain Kronecker coefficients. While tensors are an interesting test bed for GCT ideas, the far-away goal is the separation of algebraic complexity classes. The role of the Kronecker coefficients in that setting is taken by the so-called plethysm coefficients: These are the multiplicities in the coordinate rings of spaces of polynomials. Even though several hardness results for Kronecker coefficients are known, there are almost no results about the complexity of computing the plethysm coefficients or even deciding their positivity. In this paper we show that deciding positivity of plethysm coefficients is NP-hard, and that computing plethysm coefficients is #P-hard. In fact, both problems remain hard even if the inner parameter of the plethysm coefficient is fixed. In this way we obtain an inner versus outer contrast: If the outer parameter of the plethysm coefficient is fixed, then the plethysm coefficient can be computed in polynomial time. Moreover, we derive new lower and upper bounds and in special cases even combinatorial descriptions for plethysm coefficients, which we consider to be of independent interest. Our technique uses discrete tomography in a more refined way than the recent work on Kronecker coefficients by Ikenmeyer, Mulmuley, and Walter (Comput Compl 2017). This makes our work the first to apply techniques from discrete tomography to the study of plethysm coefficients. Quite surprisingly, that interpretation also leads to new equalities between certain plethysm coefficients and Kronecker coefficients.
rate research
Read More
This article describes a {em nonstandard} quantum group that may be used to derive a positive formula for the plethysm problem, just as the standard (Drinfeld-Jimbo) quantum group can be used to derive the positive Littlewood-Richardson rule for arbitrary complex semisimple Lie groups. The sequel cite{GCT8} gives conjecturally correct algorithms to construct canonical bases of the coordinate rings of these nonstandard quantum groups and canonical bases of the dually paired nonstandard deformations of the symmetric group algebra. A positive $#P$-formula for the plethysm constant follows from the conjectural properties of these canonical bases and the duality and reciprocity conjectures herein.
Computers are known to solve a wide spectrum of problems, however not all problems are computationally solvable. Further, the solvable problems themselves vary on the amount of computational resources they require for being solved. The rigorous analysis of problems and assigning them to complexity classes what makes up the immense field of complexity theory. Do protein folding and sudoku have something in common? It might not seem so but complexity theory tells us that if we had an algorithm that could solve sudoku efficiently then we could adapt it to predict for protein folding. This same property is held by classic platformer games such as Super Mario Bros, which was proven to be NP-complete by Erik Demaine et. al. This article attempts to review the analysis of classical platformer games. Here, we explore the field of complexity theory through a broad survey of literature and then use it to prove that that solving a generalized level in the game Celeste is NP-complete. Later, we also show how a small change in it makes the game presumably harder to compute. Various abstractions and formalisms related to modelling of games in general (namely game theory and constraint logic) and 2D platformer video games, including the generalized meta-theorems originally formulated by Giovanni Viglietta are also presented.
We analyze the computational complexity of optimally playing the two-player board game Push Fight, generalized to an arbitrary board and number of pieces. We prove that the game is PSPACE-hard to decide who will win from a given position, even for simple (almost rectangular) hole-free boards. We also analyze the mate-in-1 problem: can the player win in a single turn? One turn in Push Fight consists of up to two moves followed by a mandatory push. With these rules, or generalizing the number of allowed moves to any constant, we show mate-in-1 can be solved in polynomial time. If, however, the number of moves per turn is part of the input, the problem becomes NP-complete. On the other hand, without any limit on the number of moves per turn, the problem becomes polynomially solvable again.
We describe the Turing Machine, list some of its many influences on the theory of computation and complexity of computations, and illustrate its importance.
The bribery problem in election has received considerable attention in the literature, upon which various algorithmic and complexity results have been obtained. It is thus natural to ask whether we can protect an election from potential bribery. We assume that the protector can protect a voter with some cost (e.g., by isolating the voter from potential bribers). A protected voter cannot be bribed. Under this setting, we consider the following bi-level decision problem: Is it possible for the protector to protect a proper subset of voters such that no briber with a fixed budget on bribery can alter the election result? The goal of this paper is to give a full picture on the complexity of protection problems. We give an extensive study on the protection problem and provide algorithmic and complexity results. Comparing our results with that on the bribery problems, we observe that the protection problem is in general significantly harder. Indeed, it becomes $sum_{p}^2$-complete even for very restricted special cases, while most bribery problems lie in NP. However, it is not necessarily the case that the protection problem is always harder. Some of the protection problems can still be solved in polynomial time, while some of them remain as hard as the bribery problem under the same setting.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
