CORRETA

Veja: "Temos certeza que elas voltarão logo"

Inicialmente, gostaria de fazer uma observação quanto à concordância nominal dessa frase.

A palavra "certeza" neste contexto, pede a preposição "de" --> quem tem certeza, tem certeza de algo.

Embora haja que entenda pela facultatividade dessa preposição, a norma culta a exige, de modo que o correto seria: "Temos certeza de que elas voltarão logo".

Mas pulemos esse detalhe e vamos prestar atenção na estrutura da oração.

"Certeza" é substantivo e, como tal, pode receber determinado tipo de complemento. Aqui ingressamos naquela velha dúvida sobre a natureza dele: adjunto adnominal ou complemento nominal?

Por se tratar de um substantivo abstrato, já podemos constatar que tudo aquilo que vem depois da expressão "certeza" se trata de um complemento nominal. Observe (vou acrescentar a preposição "de" porque meus ouvidos se incomodam sem ela rsrsrs):

"Temos certeza (de) que elas voltarão logo" --> Temos certeza DISSO

Note, a palavra "que" exerce função de conjunção integrante e por esse motivo inaugura as orações subordinadas substantivas (ou seja, temos uma oração que equivale a um substantivo, por isso costumamos substituí-la por ISSO).

Vamos fracionar as orações:

1) Temos certeza --> oração principal;

2) (de) que elas voltarão logo --> oração subordinada substantiva.

Assim, como explanado acima, tendo em vista que a expressão "(de) que elas voltarão logo" é complemento nominal de "certeza", é possível concluir que se trata de uma oração subordinada substantiva completiva nominal.