L’origine semble venir d’une autre expression figurée: le nœud du problème.

Fig. Difficulté principale, point essentiel d’une affaire, d’une question. Voilà le nœud du problème, du débat. Trancher le nœud de la question, de la difficulté.

^{Source: https://www.dictionnaire-academie.fr/article/A9N0524}

En ce sens, vu que couper et trancher sont des synonymes, il devient évident que le plus simple pour résoudre un problème, en s’attaquant, donc, au nœud du problème est de le couper, ou le trancher, et non d’essayer de le démêler.

Trancher s’emploie aussi figurément. Trancher la difficulté, le nœud de la difficulté, Résoudre tout d’un coup une question difficile ; lever tout d’un coup un obstacle, une difficulté.

^{Source: https://www.dictionnaire-academie.fr/article/A8T0998}

Trancher le nœud du problème est donc un synonyme de décider de la solution à utiliser pour résoudre un problème, et, à force de sous-entendus, trancher, serait donc devenu un synonyme figuré de décider.

Je ne suis donc pas certain, ici, que le nœud gordien soit l’expression qui soit apparue en premier, ou si c’est une de ces expressions métaphoriques basées sur la mythologie romaine comme riche comme Crésus ou se croire sorti de la cuisse de Jupiter dont le français est friand, vu ses racines latines.