Resumen
Chen and Flum showed that any FPT-approximation of the k-Clique problem is not in para-??????
AC
0
and the k-DominatingSet (k-DomSet) problem could not be computed by para-??????
AC
0
circuits. It is natural to ask whether the ??(??)
f
(
k
)
-approximation of the k-DomSet problem is in para-??????
AC
0
for some computable function f. Very recently it was proved that assuming ??[??]???????
W
[
1
]
?
FPT
, the k-DomSet problem cannot be ??(??)
f
(
k
)
-approximated by FPT algorithms for any computable function f by S., Laekhanukit and Manurangsi and Lin, seperately. We observe that the constructions used in Lin?s work can be carried out using constant-depth circuits, and thus we prove that para-??????
AC
0
circuits could not approximate this problem with ratio ??(??)
f
(
k
)
for any computable function f. Moreover, under the hypothesis that the 3-CNF-SAT problem cannot be computed by constant-depth circuits of size 2????
2
e
n
for some ??>0
e
>
0
, we show that constant-depth circuits of size ????(??)
n
o
(
k
)
cannot distinguish graphs whose dominating numbers are either =k or >(log??3loglog??)1/??
log
n
3
log
log
n
1
/
k
. However, we find that the hypothesis may be hard to settle by showing that it implies ???????????
NP
?
NC
1
.