Descriptive complexity gives one a logic or at least a logic to express languages in a complexity class. The PH can be defined as the union of all classes that can be expressed in Second order logic. In average case complexity, Levin showed that the class $distNP$ is the average case analogue of $NP$. Such average case results give a better understanding of the search vs decision problem. But to extend further the notion of such distribution ($distNP$) over to descriptive complexity, are there any classes - possibly like $distSO\exists$ distibutional Second Order NP (there is no class like this but is only to illustrate the descriptive characterization of an average case class)? Any relationships (results) in average case complexity studied with the prism of descriptive complexity?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ If you have a descriptive complexity representation, it makes the corresponding class computably enumerable. Some complexity classes, we don't know if they have such computable enumeration, we only have semantic representation. see cstheory.stackexchange.com/q/1233 $\endgroup$– KavehJul 25 at 0:32
Add a comment
|