3

The phrase "order of magnitude" is used to indicate differences between quantities in terms of exponential powers. I've also seen it to indicate Big-Oh differences in algorithm run times.

However, in computer science there is also a notion of classifying problems in terms of their qualitative difficulty. This is the categorization of P, NP, NP Hard, NP Complete, etc. I don't think saying that an NP problem is an "order of magnitude" harder than a P problem is well-defined. Is there a different phrase which suggests the qualitative jump in problem difficulty?

herisson
  • 81,803
quiet
  • 195
  • Degree of difficulty? –  Jun 24 '15 at 16:48
  • Order of difficulty. Provided there's an established scale, order takes the name of the scale as its qualifier. "This problem is harder than that by two orders of difficulty." – StoneyB on hiatus Jun 24 '15 at 16:48
  • I agree your assertion to the contrary: "saying that an NP problem is an 'order of magnitude' harder than a P problem is well defined." But I commonly hear "order of magnitude" used to describe problems that are difficult to quantify, despite its very scientific-and-accurate sound. When someone says, "It's an order of magnitude more difficult to fly a plane than to drive a car," they are not saying that you have 10^3 versus 10^2 rules to remember or 2^4 versus 2^3 things to check before you depart. The phrase is being used for a qualitative change, not a well defined quantitative one. – rajah9 Jun 24 '15 at 16:56
  • 2
    @rajah9 I am asking from a context where extending the definition of "order of magnitude" to qualitative differences would be considered misuse and ambiguous, even if colloquially acceptable. – quiet Jun 24 '15 at 17:02
  • @StoneyB I'm not sure what the proper etiquette on EnglishSE is, but your comment is one I would accept as the answer if you posted it as such. – quiet Jun 24 '15 at 17:24

2 Answers2

1

I think level is a suitable word.

Specifically in the context of the polynomial hierarchy, one might informally think of a problem known to be NP-complete as one level harder than a problem in P (provided of course the hierarchy does not collapse at this level).

More generally, level generally connotes stratification in terms of achievement/difficulty. It's a gamey word, for example: your average computer game addict is usually fairly obsessed with the level achieved so far.

anemone
  • 6,216
1

Complexity. For this Big-O Know thy complexities! cheat sheet, it explicitly divides algorithms into time complexity and space complexity.

The big-O originally stands for "order of" ("Ordnung", Bachmann 1894), and is thus a roman letter. (source)

An NP hard problem is one order of complexity greater than an NP problem.

Going back to the cheat sheet, a Bubble sort is one order of time complexity worse than a Quicksort.

rajah9
  • 16,242