single word requests - "Order of magnitude" for qualitative changes


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?



Answer



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.


Comments

Post a Comment

Popular posts from this blog

commas - Does this sentence have too many subjunctives?

Does this sentence have too many subjunctives? If it please the king, let it be decreed that they be destroyed, and I will pay 10,000 talents of silver into the hands of those who have charge of the king's business, that they may put it into the king's treasuries. I am stumped by this sentence construction. First, there is "Let it be," which is a common English idiomatic phrase, but then it follows another subjunctive. Is that to say you can actually have a subjunctive followed by another subjunctive? Also, why does the sentence use "please"? If that's the subjunctive tense there, then why is it followed by another subjunctive instead of a conditional, or maybe "Let it be" is the conditional? Lastly, I wish to know how the that is used in the sentence. Perhaps, the simplified sentence can be restated like so: Let it be decreed that they be destroyed and that they may put it into the king's treasuries. If not, maybe the simplified sent...
Read more

verbs - "Baby is creeping" vs. "baby is crawling" in AmE

Years and years ago, I remember reading in a book on AmE usage that the phrasal turn a baby creeps before it walks was to some extent more common to AmE than to BrE, which preferred exclusively the "crawl" version. And so, I just recently checked on the accuracy of that information on NGram Viewer , and it actually was fact... more than a century ago! What I would like you to tell is if it would sound sort of weird to hear someone say today in the US that a child "creeps" before walking and running (see Synonyms ) rather than it crawls. Also, what's the story to those terms? How did "to crawl" come to prevail and supersede "to creep" to describe the way a baby moves around? As with a plant, so with a child. His mind grows by natural stages. A child creeps before he walks , sits before he stands, cries before he laughs, babbles before he talks, draws a circle before he draws a square, lies before he tells the truth, and is selfish before he ...
Read more

time - English notation for hour, minutes and seconds

I often see English notation about time using the " and ' symbols. I have always mistaken about the two, and even their meaning. I'm more used to "01:05:56", for example. How do you represent the hour, minutes, and seconds using the apostrophe and quotes punctuations? Which is for the hour, which is for minutes, and which is for seconds? Is it the common way to write duration of time elapsed? Do they have a special pronunciation? Answer It's not particularly common for expressions of time. It's similar to degrees-minutes-seconds: instead of decimal degrees (38.897212°,-77.036519°) you write (38° 53′ 49.9632″, -77° 2′ 11.4678″). Both are derived from a sexagesimal counting system such as that devised in Ancient Babylon: the single prime represents the first sexagesimal division and the second the next, and so on. 17th-century astronomers used a third division of 1/60th of a second. The advantage of using minute and second symbols for time is that it o...
Read more

etymology - Origin of "s--t eating grin"

What is the origin of the phrase shit eating grin ? How did it come to mean showing smugness or self-satisfaction of an individual's actions? Answer From the Urban Dictionary: ...these uses are documented in the Oxford English Dictionary no earlier than 1957 There have been similar expressions used quite far back: In Book XXI of his History of Rome, Livy describes a Carthaginian sect of coprophages, the risus faecivorus, or shit-eating grin, being commonly displayed by its adherents. Although, its origin is undetermined, they may have been incidents which caused the invention of this phrase. Below is an excerpt: "1944 Jrnl. Nerv. & Mental Dis. XCIX. 959 Among demented patients in advanced stages of their illness,..it is not rare to see some of them grasp their own feces, chew them and eat them often with great pleasure and satisfaction (coprophagia).
Read more

grammatical number - Use of lone apostrophe for plural?

I've been reading William Manchester's book "American Caesar", which is about Douglas MacArthur, and I found that he uses a strange convention for pluralizing the family name. When talking about the MacArthurs as a whole, he writes MacArthur' with an apostrophe, as in "After the war, the MacArthur' lived in Tokyo while the general was proconsul" (yes, he uses that term to describe him). I have never seen or heard of a rule that would prescribe this. Manchester is a bit old-timey in his style: for example, he also writes "in behalf of" instead of "on behalf of", which is the only one I have ever seen. So perhaps this is similar. Where does he get this apostrophe from? Edit: There seems to be some difficulty finding examples, which is odd. Here is a direct link to a page from Google Books that shows the apostrophe.
Read more

etymology - Where does the phrase "doctored" originate?

This is a phrase I’m particularly confused about, because it’s used often when something is manipulated or changed. For example, sometimes images surface online that are clearly Photoshopped, but people refer to them as “doctored” images. Why use the word “doctored” here? Answer The earliest Google Books match for an instance of doctored in a transitional (or perhaps post-transitional) sense between "amended" and "adulterated" appears in William Marshall, The Rural Economy of Glocestershire; Including Its Dairy: Together with the Dairy Management of North Wiltshire, and the Management of Orchards and Fruit Liquor, in Herefordshire , volume 2 (1789): Men in general, however, whose palates are set to rough cider, consider the common sweet sort as an effeminate beverage; and rough cider, properly manufactured, is probably the most generous liquor; being deemed more wholesome, to habits in general, than sweet cider:—even when genuine. That which is drank, in the kingd...
Read more

single word requests - What do you call hypothetical inhabitants living on the Moon?

I'm writing a fiction where inhabitants live on the Moon, so I want a name for them. I know that 'venusian' means 'of or relating to the planet Venus', 'martian' means 'of or relating to the planet Mars or its hypothetical inhabitants' and so on. But, after having observed that 'moonian' is not a word, I wonder as to whether there is a term meaning 'of or relating to the Moon or its hypothetical inhabitants'.
Read more