Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EXPRESSIVENESS:
Reports tagged with expressiveness:
TR06-014 | 20th December 2005
Argimiro Arratia, Carlos E. Ortiz

On a syntactic approximation to logics that capture complexity classes

We 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} ... more >>>




ISSN 1433-8092 | Imprint