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.