A category of NP-complete problems?
The area you want to look at is called "implicit complexity theory". A random and incomplete fistful of names to Google for are Martin Hofmann, Patrick Baillot, Ugo Dal Lago, Simona Ronchi Della Rocca, and Kazushige Terui. 

The basic technique is to relate complexity classes to subsystems of linear logic (the so-called "light linear logics"), with the idea that the cut-elimination for the logical system should be complete for the given complexity class (such as LOGSPACE, PTIME, etc). Then via Curry-Howard you get out a programming language in which precisely the programs in the given class are expressible. As you might expect from the mention of linear logic, these all these systems then give rise to monoidal closed categories of various flavors, which leaves you with a purely algebraic and machine-independent characterization of various complexity classes. 

One of the things that make this area interesting is that neither traditional complexity nor logical/PL methods are entirely appropriate. 

Since the categories involved typically have closed structure, the combinatoric methods favored by complexity theorists often break down (since higher-order programs tend to resist combinatorial characterizations). A typical example of this is the failure of syntactic methods to handle contextual equivalence. Similarly, the methods of semantics also have trouble, since they are often too extensional (since traditionally semanticists have wanted to hide the internal structure of functions). The simplest example I know here is the closure of LOGSPACE under composition: this is AFAIK only possible due to dovetailing and selective recomputation, and you can't treat the problems as pure black boxes.

You will likely also want to have some familiarity with game semantics and Girard's Geometry of Interaction (and their precursor, Kahn-Plotkin-Berry's concrete data structures) if you get seriously into this area -- the ideas of token-passing representations of higher-order computations used in this work supply a lot of the intuitions for ICC.

Since I've pointed out the central role of monoidal categories in this work, you might reasonably wonder about the connections to Mulmuley's GCT. Unfortunately, I can't help you here, since I simply don't know enough. Paul-André Melliès might be a good person to ask, though.