ﻻ يوجد ملخص باللغة العربية
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.
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 hi
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 theo
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 nbimat
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 Vi
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 sim