Descriptive complexity theory is the study of logical
characterizations of complexity classes, which provides us with a unique
perspective of computation theory. Nowadays, finding PTIME logic is a
main task in descriptive complexity theory. While in this dissertation,
let's focus our eyes on the limited nondeterminism classes, especially
the class βP, which is between P and NP. And we especially consider the
nondeterminism limited by the poly-logarithmic functions, so we
introduce second-order quantifiers with the poly-logarithmic functions,
which we call log-quantifiers. Using log-quantifiers, we have defined a
series of new logics, which we call log-quantifier logics. We prove that
they have a property that SO does not, that is, every formula of
log-quantifier logic can turn to a form in which only binary relations
are quantified. Then we prove that the existential fragments capture the
corresponding Guess-then-Check complexity classes on ordered structures,
especially Σ^{plog}-IFP captures βP on ordered structures.

We also extend the classic methods in descriptive complexity theory,
i.e., game method and 0-1 laws, to study the expressive power of
log-quantifiers. We introduce the relation admitting arity and height.
With this method, we prove that our logical characterization is not a
strong one. We have also proved a sufficient condition of that "FO
enclosed with log-quantifiers cannot distinguish two strings." This
condition implies that any regular language definable in this logic is
exactly FO-definable, and FO enclosed with log-quantifiers and MSO are
not comparable on strings. As for 0-1 laws, we show that log-quantifier
logics behave like second-order logic. Any logic stronger than
Σ^{log2}-DTC or Π^{log2}-DTC does
not have a 0-1 law.