We show that it is NP-hard to 2nk-approximate the integral of a positive, smooth, polynomialtime computable n-variate function, for any fixed integer k. 1
In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which s-variate problems can be approximated to within ε by using, say, polynomially many in s and ε−1 function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with ε−1 replaced by 1+logε−1. In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of s and 1+logε−1. The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.
We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by Δ the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an ϵ-approximate solution for this problem by solving a number of integer linear programs whose constraint matrices have subdeterminants bounded by Δ in absolute value. The number of these integer linear programs is polynomial in the dimension n, in Δ, and in 1/ϵ, provided that the number k of variables that appear nonlinearly in the objective is fixed. As a corollary, we obtain the first polynomial-time approximation algorithm for separable concave integer quadratic programming with Δ≤2 and k fixed. In the totally unimodular case Δ=1, we give an improved algorithm that only needs to solve a number of linear programs that is polynomial in 1/ϵ and is independent of n, provided that k is fixed.
Matrix permanents are hard to compute or even estimate in general. It had been previously suggested that the permanents of Positive Semidefinite (PSD) matrices may have efficient approximations. By relating PSD permanents to a task in quantum state tomography, we show that PSD permanents are NP-hard to approximate within a constant factor, and so admit no polynomial-time approximation scheme (unless P=NP). We also establish that several natural tasks in quantum state tomography, even approximately, are NP-hard in the dimension of the Hilbert space. These state tomography tasks therefore remain hard even with only logarithmically few qubits.