Or by experience and learning from other sucessful bridges? Stone bridges were not new in the year 1000.
There is a roman bridge that was allmost completely surviving all this time, till it was blown up in WW2:
https://en.m.wikipedia.org/wiki/Ponte_Pietra_(Verona)
If they wanted a cheap solution, they would have used wood. But wood does not last a 1000 years.
Personally I salute anyone, who can build something that lasts that long.
"including only what is barely necessary."
And "barely necessary" in solid engineering includes lots of safety margins. Not barely standing.
And yes, that includes not using more than you need, because the more material you use, the heavier your bridge is -> the greater are the forces on the structure itself even with no one passing over it.
There are some fun games out there on various plattforms, google "bridge builder"
Not a scientific simulation of course, but they do show the concept.
The 1000 year medieval bridge we're talking about could have been an efficient design for its time.
But then one must make clear: necessary for what.
I think there is a great overlap between "holds for whatever scheme the prefecture will do to test it while I stand under" and "holds for a thousand years".
There is like a limit where fatigue stress stops being a thing in a cycle graph. Many failure modes is due to penny wise cost cutting.
But I think the true definition of engineering has to encompass a level of efficiency through design, calculation and rationalization. In other words, echoing what the original commenter said, including only what is barely necessary.