by Tomás Feder
Recent work in the theory of computation has exposed the interconnectedness of three disciplines: logic, mathematics, and computational complexity.
The relationship between computational complexity and logic is exemplified by two basic results: Fagin shows that the class nondeterministic polynomial time, or NP, corresponds to existential second order logic. Papadimitriou shows that the class deterministic polynomial time, or P, corresponds to Datalog with successor and negation.
This reveals the need to understand, from a mathematical point of view, the relationship between P and NP: Given a question in NP, perhaps given by an existential second order formula, what makes it possible to answer the question in polynomial time? In general, this question turns out to be undecidable, unless P=NP. In fact, the work of Ladner via diagonalization exhibits an infinitely complex structure within NP up to polynomial time reduction.
In practice, however, the presence of mathematical structure often leads to polynomial time algorithms. Such a project cannot be carried out in general because of undecidability. This leads to the formulation, by Feder and Vardi, of a more restrictive logic, namely monotone monadic strict NP without inequality, or MMSNP. All three restrictions on SNP are imposed because with just two restrictions, the computational expressibility is the same as that of NP.
Group theoretic algorithms for computational problems had been previously obtained. However, for these problems, the starting point was itself group theoretic, involving groups and subgroups. In the work of Feder and Vardi, the initial motivation is to understand the computational structure of the entire class MMSNP, without favoring any problem over any other. A first look identifies problems corresponding to Datalog without negation or without successor. Getting beyond this first layer suggests a property called the ability to coupt, that leads immediately to problems involving groups and subgroups, in the case of abelian or commutative groups. However, when commutativity is dropped, the delineating boundary between polynomial and NP-complete problems leads to a new notion, that of a near subgroup.
1) Traditionally, group theory has involved the study of groups and their subgroups. On the other hand, when the study starts with a computational motivation, the near subgroups turn out to constitute the core. Aschbacher's work indicates that near subgroups have a rich structure.
2) Similar phenomena arise in related attempts at classification. While there is an extensive theory of matroids, in the study of parity and intersection problems, the delineating boundary avoiding NP-completeness is given by generalized matroids, as shown by Feder and Ford.
3) Similarly, the network stability problems obtained by Mayr and Subgramanian in their generalization of stable marriage are scatter free networks. However, the delineating boundary between polynomial and NP-complete cases is given by adjacency preserving, or nonexpansive networks, as shown by Feder.
In all three cases, greater generality in the mathematical structure is obtained with a computational lens, namely delineating, the boundary between computational tractability and intractability.
From a philosophical point of view, logic identifies an initial purpose, while computational complexity aims at determining whether this purpose can be achieved in practice. This feasibility criterion is what brings mathematical structure (groups with near sugroups, generalized matroids, nonexpansive networks, and families of graphs such as bipartite, interval, chordal, or perfect graphs) to the surface.
This phenomenon is, in a sense, not new. Much group theory arose out of the purpose of understanding solvability of equations by radicals, in some sense a practical concern. Here, however, the concern is given by logic formulation and the measure of practicality by computational complexity. Mathematics bridges the gap between these two.