Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputing Spectra -- On the Solvability Complexity Index Hierarchy and Towers of Algorithms
62
0
0.0
(
0
)
Added by
Matthew Colbrook
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper establishes some of the fundamental barriers in the theory of computations and finally settles the long-standing computational spectral problem. That is to determine the existence of algorithms that can compute spectra $mathrm{sp}(A)$ of classes of bounded operators $A = {a_{ij}}_{i,j in mathbb{N}} in mathcal{B}(l^2(mathbb{N}))$, given the matrix elements ${a_{ij}}_{i,j in mathbb{N}}$, that are sharp in the sense that they achieve the boundary of what a digital computer can achieve. Similarly, for a Schrodinger operator $H = -Delta+V$, determine the existence of algorithms that can compute the spectrum $mathrm{sp}(H)$ given point samples of the potential function $V$. In order to solve these problems, we establish the Solvability Complexity Index (SCI) hierarchy and provide a collection of new algorithms that allow for problems that were previously out of reach. The SCI is the smallest number of limits needed in the computation, yielding a classification hierarchy for all types of problems in computational mathematics that determines the boundaries of what computers can achieve in scientific computing. In addition, the SCI hierarchy provides classifications of computational problems that can be used in computer-assisted proofs. The SCI hierarchy captures many key computational issues in the history of mathematics including the insolvability of the quintic, Smales problem on the existence of iterative generally convergent algorithm for polynomial root finding, the computational spectral problem, inverse problems, optimisation etc.
rate research
Read More
The problem of computing spectra of operators is arguably one of the most investigated areas of computational mathematics. Recent progress and the current paper reveal that, unlike the finite-dimensional case, infinite-dimensional problems yield a highly intricate infinite classification theory determining which spectral problems can be solved and with which type of algorithms. Classifying spectral problems and providing optimal algorithms is uncharted territory in the foundations of computational mathematics. This paper is the first of a two-part series establishing the foundations of computational spectral theory through the Solvability Complexity Index (SCI) hierarchy and has three purposes. First, we establish answers to many longstanding open questions on the existence of algorithms. We show that for large classes of partial differential operators on unbounded domains, spectra can be computed with error control from point sampling operator coefficients. Further results include computing spectra of operators on graphs with error control, the spectral gap problem, spectral classifications, and discrete spectra, multiplicities and eigenspaces. Second, these classifications determine which types of problems can be used in computer-assisted proofs. The theory for this is virtually non-existent, and we provide some of the first results in this infinite classification theory. Third, our proofs are constructive, yielding a library of new algorithms and techniques that handle problems that before were out of reach. We show several examples on contemporary problems in the physical sciences. Our approach is closely related to Smales program on the foundations of computational mathematics initiated in the 1980s, as many spectral problems can only be computed via several limits, a phenomenon shared with the foundations of polynomial root finding with rational maps, as proved by McMullen.
Given a binary dominance relation on a set of alternatives, a common thread in the social sciences is to identify subsets of alternatives that satisfy certain notions of stability. Examples can be found in areas as diverse as voting theory, game theory, and argumentation theory. Brandt and Fischer [BF08] proved that it is NP-hard to decide whether an alternative is contained in some inclusion-minimal upward or downward covering set. For both problems, we raise this lower bound to the Theta_{2}^{p} level of the polynomial hierarchy and provide a Sigma_{2}^{p} upper bound. Relatedly, we show that a variety of other natural problems regarding minimal or minimum-size covering sets are hard or complete for either of NP, coNP, and Theta_{2}^{p}. An important consequence of our results is that neither minimal upward nor minimal downward covering sets (even when guaranteed to exist) can be computed in polynomial time unless P=NP. This sharply contrasts with Brandt and Fischers result that minimal bidirectional covering sets (i.e., sets that are both minimal upward and minimal downward covering sets) are polynomial-time computable.
We show that the BIMATRIX game does not have a fully polynomial-time approximation scheme, unless PPAD is in P. In other words, no algorithm with time polynomial in n and 1/epsilon can compute an epsilon-approximate Nash equilibrium of an n by nbimatrix game, unless PPAD is in P. Instrumental to our proof, we introduce a new discrete fixed-point problem on a high-dimensional cube with a constant side-length, such as on an n-dimensional cube with side-length 7, and show that they are PPAD-complete. Furthermore, we prove, unless PPAD is in RP, that the smoothed complexity of the Lemke-Howson algorithm or any algorithm for computing a Nash equilibrium of a bimatrix game is polynomial in n and 1/sigma under perturbations with magnitude sigma. Our result answers a major open question in the smoothed analysis of algorithms and the approximation of Nash equilibria.
In the study of differential privacy, composition theorems (starting with the original paper of Dwork, McSherry, Nissim, and Smith (TCC06)) bound the degradation of privacy when composing several differentially private algorithms. Kairouz, Oh, and Viswanath (ICML15) showed how to compute the optimal bound for composing $k$ arbitrary $(epsilon,delta)$-differentially private algorithms. We characterize the optimal composition for the more general case of $k$ arbitrary $(epsilon_{1},delta_{1}),ldots,(epsilon_{k},delta_{k})$-differentially private algorithms where the privacy parameters may differ for each algorithm in the composition. We show that computing the optimal composition in general is $#$P-complete. Since computing optimal composition exactly is infeasible (unless FP=$#$P), we give an approximation algorithm that computes the composition to arbitrary accuracy in polynomial time. The algorithm is a modification of Dyers dynamic programming approach to approximately counting solutions to knapsack problems (STOC03).
This article describes the solvability of HornSAT and CNFSAT. Unsatisfiable HornCNF have partially ordered set that is made by causation of each clauses. In this partially ordered set, Truth value assignment that is false in each clauses become simply connected space. Therefore, if we reduce CNFSAT to HornSAT, we must make such partially ordered set in HornSAT. But CNFSAT have correlations of each clauses, the partially ordered set is not in polynomial size. Therefore, we cannot reduce CNFSAT to HornSAT in polynomial size.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
