How do I tell a "project lead" to f--k off and learn some computer science when he tells me to do something that amounts to solving a generic Travelling salesman problem in linear time.
One of his insights was: 1,000 nodes takes only 1 second then 30,000 should take 30 seconds. I'm not up to teaching combinatorics and Big O to idiots.
[edited]
How do I educate my coworkers or boss in this problem domain without making him look like an idiot?
Just explain to him that it can't be done. What else can you do?
I'd just be really, really sure you're correct. (Not saying that you aren't correct, but pride goeth before the fall.)
Your boss may not know much about hard graph problems, but are you so sure this is impossible? For one thing, many problems are not as general as full TSP. Are you sure your problem doesn't reduce to finding a Hamiltonian cycle, for example? Perhaps your graph has geometric features which can reduce the complexity? For example, does it satisfy the triangle inequality?
Regardless, for most real applications coming close to the optimal solution (as opposed to solving exactly) is perfectly acceptable. In the case of traveling salesman and related problems, there are many heuristics which can achieve this. Have you considered and rejected branch and bound, cutting plane methods, minimum spanning trees, simulated annealing, or Kernighan-Lin heuristics?
In my experience, real-life problems often have weaknesses that can be exploited from an algorithmic perspective. It's mostly just a question of modelling your problem correctly.
How to Win Friends and Influence People has some points here that I think are worth noting in what you are trying to do:
Begin in a friendly way.
Start with questions the other person will answer yes to.
Let the other person feel the idea is his/hers.
Call attention to other people's mistakes indirectly.
Talk about your own mistakes first.
Let the other person save face.
Give them a fine reputation to live up to.
Make the other person happy about doing what you suggest.
Those would be my suggestions for where to start.
Don't tell him it can't be done, just start explaining that it can be done ... with a quantum computer. Then of course, you'll have to explain quantum physics to him. Good luck.
This might help:
TSP explained in simple english, with very short sentences. A kid can understand it, but if a manager can understand it is a different thing.
Explain to him that if he can solve a 100 piece jigsaw puzzle in 10 minutes, it doesn't mean he can solve a 1000 piece one in under 2 hours.
