Sounds like a P/NP-type problem. It's quite a hard problem to calculate all possible permutations of routings and schedules across 5 cities ("NP"), and United'

Sounds like a P/NP-type problem. It's quite a hard problem to calculate all possible permutations of routings and schedules across 5 cities ("NP"), and United's system clearly isn't up to snuff for it, while Google's is. But validating and pricing any single itinerary is a trivially easy problem ("P"), so United can handle that no problem. It can't come up with the itinerary, but given a particular one, it will sell it to you.