Communication is key in this scenario, You've got to be explaining an under estimation as soon as you know it is.

This is more important than you think. To expand on the parent, when communicating keep in mind several extremely important goals:

- you are able to organize your work. If a problem is potentially without a solution, you're likely not going to be able to hold all of that info in your brain at all times.

- when you bring someone in to help, they could get all the context they need by reading the materials - emails, documents, comments, etc, that you already created and organized. They will likely not have all the context you have, but they will have information available and digested.

- it helps keep stakeholders up to date on the progress and risks. Maybe you are able to just talk to your boss, but you don't want to repeat all of that each time you tell someone new. You don't want to setup a meeting just to update your stakeholders

- in case you are able to solve the problem, the materials you write while solving the problem will serve as a staring point for the documentation of the feature/product

Expectation management. Be predictable in your output even if it means being a bit worse on average. If you occasionally perform miracles, don’t be surprised when people show up asking for more miracles.

I’d start by not telling my boss it’ll take two weeks to solve a problem that might not have a solution.

This is why I prefer to commit to stages of development, rather than a shipping feature, for things that require research. If possible, I will absolutely try to avoid giving a target date for a feature until I've already got a prototype working. I will give a target date for the prototype, though... even though that number is far more often just an arbitrary date than not.

I understand that my approach frustrates managers who demand timelines. But sometimes reality interferes with those timelines, and I'm the one steeped in reality.

Deliver an approximate or good-enough solution to buy yourself time.

Which then immediately gets thrown into production and becomes the bedrock upon which further bad decisions are irreversibly built on every time, of course. Now the time pressure is even higher because people are actively complaining about the issues that cannot be solved with the hastily jerry rigged implementation ("should be simple right, just do..." is a bane of my existence).

This comment reminded me of something I read about laymen estimating the difficulty of technical problems. IIRC the two examples were:

a) Given a quality photograph, detect if it's of a bird.

b) For the same photograph, detect if it's taken in a national park.

The first problem may seem much easier if one does not know about EXIF geodata, assuming it's available in this scenario.

This is an inversion of the originating XKCD, which possible shows how far machine learning has come in the intervening years: https://xkcd.com/1425/

No, the first one is still much harder – and still seems easier to the layperson.

Just honesty. "Yes I did, I was wrong and this is why" you might get back "ok! skip that bit, it's not so important now after all"