1
$\begingroup$

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.

Are there in fact counterexamples to this claim or is it necessarily true?

$\endgroup$
2
$\begingroup$

If the greediness here means moving on the input based on a specified score, and computation of the input item's score is polynomial, the answer is yes. It is correct. Because moving on the input with $n$ items is linear, and if the scoring computation for each item will be polynomial, as sorting them will be polynomial as well; finally, we can solve the problem in polynomial time (by the greedy algorithm).

Notice that, the polynomial computability of the score is vital here. For example, if the computation of the score for each item will be an NP-complete/hard problem (for example if it is the minimum vertex covering of a graph), the statement will not be valid anymore.

$\endgroup$
2
  • $\begingroup$ Thanks for the response! Does this imply that there could be a case where the computation of the input item's score must be non-deterministic making the claim false? $\endgroup$ – DenverCoder1 Feb 15 at 13:42
  • 1
    $\begingroup$ @DenverCoder1 My pleasure. Please see the update. $\endgroup$ – OmG Feb 15 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.