Many people who criticize Complexity say that you can just increase the Threshold of the skill roll to accomodate a difficult task. This is for the most part true - and Complexity as much as its touted does not really introduce another axis to measuring character skill that wasn't already there. However by removing Complexity ratings for skills, and making the Complexity rating of a task cost dice instead of providing bonuses or penalties, you are actually introducing a second axis that was not there before.
The reason for this simple: the character has two axises - skill and talent. They don't really need a third one. Even with the task having a Complexity rating that incurs a penalty or modifier, this isn't really adding a second axis to the task itself - because all it's doing in essence is modifying the Threshold (which is the same axis that die modifiers affect)
So, to keep it in the terms of characters and tasks having two axises (skill/talent and difficulty/complexity), the Task's equivalent of skill is the Threshold. This acts against the result of the character's die roll. The Tasks equivalent of talent (complexity) acts against a different axis - the number of dice that the character is rolling.
The way this would work is that a Threshold and Complexity is set. The Complexity reduces the character's effective skill level (i.e., the number of dice rolled). There is no buying Complexity for your skills - the only way to offset the die penalty is to have a higher skill level, a specialization that provides a bonus die, or spend Emergency Dice or genre points or something to gain dice.
It winds up being almost like one of the optional rules (where a negative difference in Complexity nets a penalty in dice while a positive difference nets a bonus on the roll). It also eliminates the whole opposed skill issue (since Skills don't have Complexity and they're acting on each other, there is no die penalty), and makes it so that high Complexity tasks are going to be much rarer.
Finally, and this is the cool thing, it also makes possible a mechanic for the character to increase the Complexity of the end result of the skill test even when the task itself does not demand a more Complex result, by sacrificing ED or skill levels.
Example: A character needs to defuse a bomb, quickly. The GM rules that the bomb is fairly normal, and can be defused with a Complexity 1 task but that it raises the possibility of the PC being caught, unless the character has another means to speed up the process (like a special ability or a tool that makes it faster or something). The GM also rules that by sacrificing two dice to hurry the defusing process, it is guaranteed that the character won't get caught - at the sacrifice of an increased chance of failure. It also means that there might be Perks or Flaws that increase the default Complexity of certain tasks. I still need to think about how this would affect attribute checks, but I think it would work unmodified. Unskilled rolls might definitely need to be looked at closely...
Interestingly enough, this model also lends itself very well to [i]frustration[/i] mechanics. So the guy defusing the bomb isn't in danger of being caught, and has time for a few attempts. Each time he fails and reattempts, it increases the Complexity of the task and, as a result, drops a die from his skill roll.
I'm seriously considering implementing this as a house rule in my games.