ECCC-Report TR06-014https://eccc.weizmann.ac.il/report/2006/014Comments and Revisions published for TR06-014en-usThu, 26 Jan 2006 10:38:38 +0200
Paper TR06-014
| On a syntactic approximation to logics that capture complexity classes |
Argimiro Arratia,
Carlos E. Ortiz
https://eccc.weizmann.ac.il/report/2006/014We formulate a formal syntax of approximate formulas for the logic with counting
quantifiers, $\mathcal{SOLP}$, studied by us in \cite{aaco06}, where we showed the
following facts:
$(i)$ In the presence of a built--in (linear) order, $\mathcal{SOLP}$ can
describe {\bf NP}--complete problems and fragments of it capture classes like
{\bf P} and {\bf NL};
$(ii)$ weakening the ordering relation to an almost order (in the sense of \cite{LW02})
we can separate meaningful fragments, using a combinatorial tool suited for these languages.
The purpose of the approximate formulas
is to provide a syntactic approximation to logics contained in
$\mathcal{SOLP}$ with built-in order,
that should be complementary of the semantic approximation based on almost orders, by producing approximating logics where
problems are described within a small counting error.
We introduce a concept of {\em strong expressibility} based on approximate formulas, and show that for many fragments of $\mathcal{SOLP}$ with built-in order, including ones that capture {\bf P} and {\bf NL}, expressibility and strong expressibility are equivalent.
We state and prove a Bridge Theorem that links
expressibility in fragments of $\mathcal{SOLP}$ over almost-ordered structures to strong expressibility with respect to approximate formulas for the corresponding fragments over ordered structures. A consequence of these results is that proving inexpressibility results over fragments of $\mathcal{SOLP}$ with built-in order can be done by proving inexpressibility over the corresponding fragments with built-in almost order, where separation proofs are easier.
Thu, 26 Jan 2006 10:38:38 +0200https://eccc.weizmann.ac.il/report/2006/014