[nilkn]

There is actually work being done on this problem, at least to some extent. A DNC, for instance, can accept variable-structure inputs by storing each piece in its external memory bank. This is illustrated in the original Nature paper by feeding in an arbitrary graph definition piece by piece, then feeding in a query about the graph.

This doesn't necessarily address all the nuances of your post, but I do believe it's a step in the right direction. It pushes networks from

"learn how to solve this completely statically defined problem via sophisticated pattern matching"

to

"learn how to interpret a query, drawn from some restricted class of possible queries; accept variable-structure input to the query; strategize about techniques for answering the query; and finally compute the answer, possibly over multiple time-steps"