8
$\begingroup$

I hope this question isn't too naive for this site.

In mathematics (topology, geometry, algebra) it is common for one to distinguish between two objects by coming up with an algebraic or numerical invariant, and proving the two objects have different values. I'm wondering to what extent this has been tried with complexity classes (or if it has, why I haven't ever heard about it). Algebraic structures show up a lot in theoretical computer science as a whole (cf Uses of algebraic structures in theoretical computer science), so why not in complexity theory?

In my naivete I can imagine a notion of equivalence of two languages: the existence of a polynomial-time reduction which is also reversible (or a bijection on the strings). I can also imagine that this notion is unsuitable: no finite languages of differing cardinality could be considered equivalent, even though we're more often interested in infinite languages.

Are there any other, weaker notions of isomorphism of languages that have yielded interesting results? Are there other kinds of numerically-flavored invariants that have been used to distinguish complexity classes?

$\endgroup$
3
  • $\begingroup$ does resource-bounded measure fit what you're looking for? $\endgroup$ Nov 28, 2012 at 20:06
  • $\begingroup$ While this is not entirely helpful, my (vague) understanding is that Mulmuley's geometric complexity program rests essentially on such an algebraic argument. More usefully, his P vs NC proof uses a counting characterization of problems computable in NC to separate it from P. $\endgroup$ Nov 29, 2012 at 4:53
  • 1
    $\begingroup$ @SashoNikolov: one issue with resource-bounded measure is that, for classes closed under finite variations (as are essentially all complexity classes we ever consider), if they are measurable they have measure either 0 or 1. In that sense, as a numerical invariant resource-bounded measure only gives you three possibilities: measure 0, measure 1, or unmeasurable. Resource-bounded dimension can provide finer distinctions... $\endgroup$ Nov 29, 2012 at 16:40

1 Answer 1

5
$\begingroup$

First of all, the relation you defined is usually called polynomial-time isomorphism ($\cong^p$). Although isomorphism is an interesting notion that has been studied, the (weaker) relation that is more frequently of concern in complexity is polynomial-time equivalence: $A$ and $B$ are equivalent ($A \equiv_m^p B$) if there are polynomial-time many-one reductions (aka Karp reductions) from $A$ to $B$ and vice versa, but those reductions need not be inverses to one another, and need not even have polynomial-time inverses. Sometimes we also care about equivalence under polynomial-time Turing reductions rather than many-one ($\equiv_T^p$), aka Cook reductions. For example, either of these notions of equivalence is "good enough" for $P$ vs $NP$ (that is, you don't need to consider isomorphism classes).

From the perspective of polynomial-time equivalence, there is partial "good reason" that you don't hear about numerical invariants: they can't work in general. A theorem in Andrew Marks's thesis states that $\equiv_T^p$ is complete for countable Borel equivalence relations (the introduction of his thesis gives a good overview of Borel equivalence relations and their significance). In particular, this implies that there is no Borel function $f: 2^{\mathbb{N}} \to \mathbb{R}$ such that $A \equiv_T^p B$ iff $f(A) = f(B)$.

The reason I say this is only partially a good reason is that there still might be a Borel function $f:2^{\mathbb{N}} \to \mathbb{R}$ such that if $f(A) \neq f(B)$ then $A \not\equiv_T^p B$. Or there might be a non-Borel function that does the job, but if there is we're a little unlikely to find it...


But classifying all equivalence classes is also stronger than what we usually care about, since the number of equivalence classes that show up as natural complexity classes is comparatively small (despite the forbidding size of the complexity zoo). However, there are other "numerical" invariants we can associate to languages. One such is their density: the density of a language $A$ is the function $d_A(n) :=$ number of strings in $A$ of length $\leq n$. Note that density is preserved, up to a polynomial change, by poly-time isomorphisms, but not necessarily by polynomial-time equivalences (e.g. all languages in $P$ are polynomial-time equivalent, but they can have wildly different densities).

We know things like: if $A$ is polynomially sparse ($d_A(n) \leq poly(n)$) then $A$ cannot be $NP$-complete unless $P=NP$ (Mahaney's Theorem). There are lots of other results about sparse languages and their relation to complexity classes. For good surveys, see Cai and Ogihara "Sparse Sets versus Complexity Classes" in Complexity Theory Retrospective II (available online - just Google) and Hemaspaandra and Glaßer's pair of articles "A Moment of Perfect Clarity I,II" in SIGACT News.


As mentioned by @SureshVenkat, you can kind of view Geometric Complexity Theory in the light you're talking about. However, the algebraic objects used there - namely representations - are more akin to general properties of a language than to numerical properties per se, but at least they are properties of an algebraic flavor.


Finally, in algebraic complexity theory one numerical property that's worth mentioning, but probably won't work to resolve the big questions, is degree. (As in the degree of a polynomial.) Strassen's degree bound is still the only known super-linear lower bound on unrestricted algebraic circuits. Degree also gets used e.g. in Razborov-Smolensky and many other areas of low-level (Boolean) circuit complexity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.