A locução «por mais que» funciona como conjunção subordinada concessiva iniciando uma oração subordinada em que se admite um facto contrário à acção principal, mas incapaz de impedi-la. Esta locução introduz orações subordinadas finitas e exige conjuntivo: «Por mais que implorasse, ele não confessou o seu erro.»
Observe-se, porém, que se usa esta locução a introduzir uma oração («por mais que estude, não consigo passar no exame») ou associada a um adjectivo, também a introduzir uma oração («por mais estudioso que seja, não consigo passar no exame»). A estrutura apresentada na pergunta é, pois, de duvidosa gramaticalidade, porque na locução se insere, em vez de um adejctivo, uma expressão preposicional («por mais que com grau diferente de complexidade»). A expressão mais correcta é: «por muito diferente que seja o grau de complexidade»). Neste caso, é preferível recorrer à locução concessiva «por muito que», visto diferente aceitar com dificuldade o grau comparativo (?«este grau de complexidade é mais diferente do que aquele»).
1 Curiosamente, parecido aceita o grau comparativo («este quadro é mais parecido com uma fotografia do que aquele»). O adjectivo igual não aceita bem o comparativo (?«este quadro é mais igual a uma fotografia do que aquele») nem o superlativo (?«este quadro é muito igual a uma fotografia»), a não ser em certos contextos.
