Q:

When designing a campaign plot, how can I test it for complexity?

I am creating plot threads for my ongoing science fiction campaign. I know my players pretty well and they do like a well interwoven set of plots. I want to make sure that the plot threads I am working on are of just the right level of complexity before I build them into my campaign.
I am looking for a process or set of steps where I can decompose the plots into their elements and then - by myself - work through the plots to get a feel for their complexity. Complexity here is how difficult the plot is to follow, which is a combination of:

Number of NPCs involved.
Number of different sub-plots going on at once.
How much these sub-plots interact with each other (you can have loads of them if they are easily separated).

The problem I have had doing this by just pretending to be the players is that I have the entire campaign plot in my head, so it is very difficult to put myself directly into the shoes of the players.
Is there a way to test my plot threads before I run them through with players?

A:

I use graph theory. All you need to do is to have NPCs (and/or places) as nodes and plots as arcs. You can even use something like GraphViz to visualise the graph you created. In general, the more complex the graph, the more potentially complex the plot.  
Each link could have a cost associated with it that depends on how hard whatever the arc represent is to find out from the PCs's point of view. Or rather what you think is the difficulty in getting that particular thread. This can be highly subjective and difficult to do as all the information you pass to the players has the same colour!  They do not know what is really important and what is not. Then you can do some "shortest path" calculations to see how reachable an end node is from any other nodes.
A limitation of this method is that it is very static -- unless you have a nice little script that you can update for all nodes/arcs as your PCs will do things that the NPCs will need to react to.

A:

I like your list but I think you're missing a factor.  Common or ambiguous elements of plots.  
Let's take one of the standard simple plots in a game.  Somebody went missing and the party has to find him or her.  Okay, you can spin off as much complexity as you want but the plot itself is basic.  
Now let's run two of those at the same time.  It seems that we've just doubled the complexity.
Okay, now put a body in the game.  To which plot does it belong?  This kind of question adds a ton of complexity to your plot (especially if there's the possibility that it ties two plots together or belongs to a third, undiscovered plot).  But this complexity only occurs when multiple are active.  So if you're breaking the game down into individual plots and counting their complexity in isolation, you'll miss something like this.
Anyway, to estimate something like this I'd right out the clues, NPCS, hints, etc that you drop and give them a point or two toward each plot they could apply to.  You could probably get fancier with the math but I don't think it's worth the trouble because the set of clue applications you come up with will probably be different than what the players think of.  
Another factor to consider is agents.  How many people are actively taking part in a plot?  A plot where the party acts as a single unit and the NPCs react only when the PCs show up is simple.  The same plot where the party is not a cohesive unit and all five of them act independently is more complex.  The same plot with two NPCs trying to cover up evidence whenever they're off stage is even more complicated.  

A:

"Complexity is how difficult the plots are to follow"
My experience is that difficulty in following plots depends on the following factors:

Clarity on the goal and role of the PCs
Clarity on the goals and roles of the NPCS
Anything that is superfluous to the above
Anything that casts doubt on #1/#2
Play expectations about how play works and how much betrayal/lying/GM gotchas to expect

I ran a one-on-one one shot which had a pretty simple setup - the bad guy needed to be killed.  Easy enough, right?   The player had his character go get his girlfriend, and find a safe place to hide her.  Ok, reasonable.  He then freaks out that the priest he's going to leave her with is secretly going to betray him...   I stop the game, I go, "Look, that's not what this game is about.  This one shot is to show off this game system, and the game system is about duels and tactical fighting.  The priest isn't going to betray you, that's not where the fun is here."
So, even when you have a dead simple plot, players might project other things onto it, if they've got bad expectations.
The better you get at giving clarity to players as a GM, the easier it is to follow the ideas and not get lost.  If you have multiple plots happening?  Make sure it's clear to the players that these are, indeed, multiple, separate plots.
Where there is to be ambiguity?  I really prefer the Dogs in the Vineyard method: "He's lying.  You're not sure why or what, but you know you're not getting the truth here."   There, the ambiguity is assigned to the character, but as the GM, the info you're getting from me is clear.  This avoids the pitfall where the players assume that everything is probably false and spend 80% of the game hyper preparing for things that don't matter.

