I can’t read those links, but determining whether an input is a minimum seems to be in co-NP because it allows easy verification of a “no” answer by counterexample. So have those people proved that NP=co-NP, or am I just being dense?
This still seems to imply that function minimization isn’t much harder than NP-complete problems.
Yep, as a programmer I should’ve said “at most polynomially harder than a problem in NP”. You’re right that my wording was bad. I still stand by the spirit, though :-)
I can’t read those links, but determining whether an input is a minimum seems to be in co-NP because it allows easy verification of a “no” answer by counterexample. So have those people proved that NP=co-NP, or am I just being dense?
Yep, as a programmer I should’ve said “at most polynomially harder than a problem in NP”. You’re right that my wording was bad. I still stand by the spirit, though :-)