Apart, perhaps, from 'gordian knot' as has already been suggested, I can't think of any word or compound with an established definition that exactly fits the bill.
So, it's been mentioned already but, to me, conundrum would work best in the sentence given
This problem is a conundrum which gets [more?] complicated every time you try to solve it.
Conundrum, of course, means:
Any puzzling question or problem; an enigmatical statement. - OED
Which, on it's own, doesn't really fit the exact requirement that the OP has posted.
However, I would argue that, in current usage, it is filling the gap.
A quick check on Google News returns these on the first page:
White House Countdown: The Ryan Conundrum
The Afghan conundrum
British farmers face conundrum: the hearts says ‘Leave’ the EU but the head says ‘Remain’
Promising Gene Therapies Pose Million-Dollar Conundrum
A political conundrum
In each of these cases the 'conundrum' is an issue or question that can be described quickly, often in a single, brief paragrapgh, but which is complicated and, often apparently unsolvable.