Displaying similar documents to “Improved Lower Bounds on the Approximability of the Traveling Salesman Problem”

Threshold Circuits for Iterated Matrix Product and Powering

Carlo Mereghetti, Beatrice Palano (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

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

Lipschitz stability in the determination of the principal part of a parabolic equation

Ganghua Yuan, Masahiro Yamamoto (2008)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

Let be one solution to t y ( t , x ) - i , j = 1 n j ( a i j ( x ) i y ( t , x ) ) = h ( t , x ) , 0 < t < T , x Ω with a non-homogeneous term , and y | ( 0 , T ) × Ω = 0 , where Ω n is a bounded domain. We discuss an inverse problem of determining unknown functions by { ν y ( h ) | ( 0 , T ) × Γ 0 , y ( h ) ( θ , · ) } 1 0 after selecting input sources h 1 , . . . , h 0 suitably, where Γ 0 is an arbitrary subboundary, ν denotes the normal derivative, 0 < θ < T and 0 . In the case of 0 = ( n + 1 ) 2 n / 2 , we prove the Lipschitz stability in the inverse problem if we choose ( h 1 , . . . , h 0 ) from a set { C 0 ( ( 0 , T ) × ω ) } 0 with an arbitrarily fixed subdomain ω Ω . Moreover we can take 0 = ( n + 3 ) n / 2 by making special choices...

Entire solutions in 2 for a class of Allen-Cahn equations

Francesca Alessio, Piero Montecchiari (2010)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

We consider a class of semilinear elliptic equations of the form 15.7cm - ε 2 Δ u ( x , y ) + a ( x ) W ' ( u ( x , y ) ) = 0 , ( x , y ) 2 where ε > 0 , a : is a periodic, positive function and W : is modeled on the classical two well Ginzburg-Landau potential W ( s ) = ( s 2 - 1 ) 2 . We look for solutions to ([see full textsee full text]) which verify the asymptotic conditions u ( x , y ) ± 1 as x ± uniformly with respect to y . We show variational methods that if is sufficiently small and is not constant, then ([see full textsee full text]) admits infinitely many of such solutions,...

Equi-integrability results for 3D-2D dimension reduction problems

Marian Bocea, Irene Fonseca (2010)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

3D-2D asymptotic analysis for thin structures rests on the mastery of scaled gradients α u ε | 1 ε 3 u ε bounded in L p ( Ω ; 9 ) , 1 < p < + . Here it is shown that, up to a subsequence, u ε may be decomposed as w ε + z ε , where z ε carries all the concentration effects, α w ε | 1 ε 3 w ε p is equi-integrable, and w ε captures the oscillatory behavior, z ε 0 in measure. In addition, if { u ε } is a recovering sequence then z ε = z ε ( x α ) nearby Ω .