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...