In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class $\#W\left[P\right]$, the parameterized analogue of $\#P$. We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.

This paper deals with lower bounds on the approximability of different subproblems of the Traveling Salesman Problem (TSP) which is known not to admit any polynomial time approximation algorithm in general (unless $𝒫=\mathrm{𝒩𝒫}$). First of all, we present an improved lower bound for the Traveling Salesman Problem with Triangle Inequality, -TSP for short. Moreover our technique, an extension of the method of Engebretsen [11], also applies to the case of relaxed and sharpened triangle inequality, respectively,...

This paper is devoted to the study of a turbulent circulation model. Equations are derived from the “Navier-Stokes turbulent kinetic energy” system. Some simplifications are performed but attention is focused on non linearities linked to turbulent eddy viscosity ${\nu }_t$. The mixing length $\ell$ acts as a parameter which controls the turbulent part in ${\nu }_t$. The main theoretical results that we have obtained concern the uniqueness of the solution for bounded eddy viscosities and small values of $\ell$...

In this paper, we consider a Borel measurable function on the space of $m\times n$ matrices $f:M^{m\times n}\to \overline{ℝ}$ taking the value $+\infty$, such that its rank-one-convex envelope $Rf$ is finite and satisfies for some fixed $p>1$: $$-c_0\le Rf\left(F\right)\le {c(1+\parallel F\parallel }^p)\text{for}\text{all}F\in M^{m\times n},$$ where $c,c_0>0$. Let $Ø$ be a given regular bounded open domain of ${ℝ}^n$. We define on $W^{1,p}(Ø;{ℝ}^m)$ the functional $$I\left(u\right)={\int }_{Ø}f\left(\nabla u\left(x\right)\right)dx.$$ Then, under some technical restrictions on $f$, we show that the relaxed functional $\overline{I}$ for the weak topology of $W^{1,p}(Ø;{ℝ}^m)$ has the integral representation: $$\overline{I}\left(u\right)={\int }_{Ø}Q\left[Rf\right]\left(\nabla u\left(x\right)\right)dx,$$ where for a given function $g$, $Qg$ denotes...

The complexity of computing, via threshold circuits, the and of fixed-dimension $k\times k$ matrices with integer or rational entries is studied. We call these two problems ${\mathrm{𝖨𝖬𝖯}}_{𝗄}$ and ${\mathrm{𝖬𝖯𝖮𝖶}}_{𝗄}$, respectively, for short. We prove that: (i) For $k\ge 2$, ${\mathrm{𝖨𝖬𝖯}}_{𝗄}$ does not belong to ${\mathrm{TC}}^0$, unless ${\mathrm{TC}}^0={\mathrm{NC}}^1$.newline (ii) For : ${\mathrm{𝖨𝖬𝖯}}_{\mathsf{2}}$ belongs to ${\mathrm{TC}}^0$ while, for $k\ge 3$, ${\mathrm{𝖨𝖬𝖯}}_{𝗄}$ does not belong to ${\mathrm{TC}}^0$, unless ${\mathrm{TC}}^0={\mathrm{NC}}^1$. (iii) For any , ${\mathrm{𝖬𝖯𝖮𝖶}}_{𝗄}$ belongs to ${\mathrm{TC}}^0$.