New answers tagged

15

To be clear, it's not meant to be formalizable. It's not a theorem, it's an observation about the world -- it's okay if "natural" is subjective here. For analogy, if someone says "differentiation is mechanics while integration is art", they're not inviting you to formalize "mechanics" and "art" and prove the statement, they're trying to convey a general ...


4

It roughly boils down to whether the problem definition could be circular: An artificial problem is one constructed to fill its class criteria. A natural problem does not rely on its method of construction to fill the class criteria. Ladner's construction is known to be NP-intermediate, provided NPI exists. Proving any candidate for NPI natural problems ...


Top 50 recent answers are included