If it is known that for some optimization problem there is a greedy algorithm that solves it and the solution includes sorting of input at the preliminary stage, is it necessarily true that the problem belongs to P?
I was told it is true that problems of this type must belong to P, but I have questions about whether this is true.
It seems to me that there should be many examples of optimization problems with non-deterministic greedy algorithms. Possibly for TSP?
Are there in fact counterexamples to this claim or is it necessarily true?