When I read the title of your question, I immediately thought of koans, and now that I see that your paper is about computational complexity, I think the word you are looking for will be found in the practice of koans or in hacker koans.
A koan is a teaching tool that presents an idea or story that cannot be resolved by brute-force logic. That attribute is analogous to a problem that is computationally expensive. You specifically used the word paradox, and many of the most well-known koans are paradoxes.
English translations of words that mean solving a koan
Translating words from Chinese and Japanese into English can be difficult if you want to accurately describe the result of solving or understanding a koan. Of course, hundreds of thousands of people have tried, so there are some good candidates. First, a general list:
- Enlightenment (this is the primary goal of Buddhism)
- Resolution, as in "to resolve"
- Unification (of the self and non-self, or seeing through the illusion of duality)
- Consciousness (a total or complete consciousness that is in opposition to the typical partially-asleep consciousness)
- (Being) awake, or awakening
Especially in computer science disciplines such as computational theory, sudden insight into a problem is common, and it almost seems inevitable that hacker koans would arise.
In one hacker koan, Master Foo tells a C programmer that even though Unix is programmed in C, one line of Unix script has more Unix-nature than 10,000 lines of C code. The koan ends with:
“And who better understands the Unix-nature?” Master Foo asked. “Is it he who writes the ten thousand lines, or he who, perceiving the emptiness of the task, gains merit by not coding?”
Upon hearing this, the programmer was enlightened.
--Master Foo and the Ten Thousand Lines
English ∩ computational complexity ∩ koans
I agree that you did not "solve" this problem. Since the word "resolved" comes from the same root as "solved", I do not think it is much better than solved even though it does sound a little better than solved.
From the above list of words, my intuition says the two best are insight and transcendence (in some form, not those exact forms of the words).
There is another option, however, that is implied by the nature of koans and apropos to your topic. Koans emphasize destroying the illusion of dualism, or said differently, identifying opposites as actually being unified. If you have identified a method for comparing the time complexity of two algorithms and your method has a time complexity that is less expensive than either of the two algorithms, then you effectively destroyed the duality-belief that computationally expensive algorithms cannot be measured with a computationally cheap algorithm. In that sense, you unified two ideas that were previously thought to be opposites.
In that sense, you have revised (revised comes from the Latin word, "to see") previously held beliefs. Or disproved, synthesized, or some other similar word.
Good luck with your paper!