1

I would essentially like communicate that solving a problem, if done through this method, would take way too long to be realistic or practical. This is a common occurrence in computer science where you can solve a problem, but your solution takes too long. I feel like

this problem requires infeasible computational resources

is essentially what I'd like to say. But I'm not sure if

this problem requires infeasibly large computational resources

is more appropriate. Does anyone have any better suggestions than these? Or do any one of these sound better for any reason?

A side question: "unfeasibly large" brings up over 300,000 search results, whereas "infeasibly large" only brings up 15,000. They both seem correct, according to an earlier question, but is there really a preference?

6
  • 4
    Does this answer your question? Alternatives to "computationally expensive"? ("computationally prohibitive", if it's "unrealistically" expensive). Sep 5, 2020 at 15:23
  • @FumbleFingers "computationally expensive" is a nice alternative, but is not the same thing as "infeasible". I would like to emphasize that it is so "expensive" that is is not "affordable", in a computational sense. "Computationally prohibitive" is probably more like it, but I wonder if there is a better alternative.
    – cartonn
    Sep 5, 2020 at 15:28
  • 2
    Starting with the most common, words that follow it is computationally in Google Books are expensive, prohibitive, infeasible. Followed by what I would say is the main "jargon" term used by theoreticians and computer specialists: computationally intractable. Sep 5, 2020 at 15:45
  • It's a resource hog.
    – Hot Licks
    Sep 5, 2020 at 17:04
  • Sometimes the result of a brute force algorithm ot perhaps a 'naive approach'. Sep 5, 2020 at 18:57

4 Answers 4

2

"The problem requires inordinate computational resources."

Inordinate : exceeding reasonable limits

Merriam Webster

Drainage system : Inordinate Delay Sparks Protest

Kashmir Age - 22 August 2020

1

This for entertainment more than application: I had a colleague who labeled some problems/project proposals as "end-of-universe." He explained that in physics there are some things that are in principle possible, but to complete would require more time than the universe will exist. It was not uncommon, when another manager proposed some particularly spectacular computer adventure, for him to say, "That's an end-of-universe idea, but we can get right on it after (FTL is invented|the Higgs boson is harnessed|some other mysterious thing)."

0

(Edit: after two comments pointing out the weakness of "nontrivial", I added the other options in order of less to most precise.)

Since you are talking about computer science, you could consider this entry from Eric S. Raymond's Jargon File:

nontrivial: adj.
Requiring real thought or significant computing power. Often used as an understated way of saying that a problem is quite difficult or impractical, or even entirely unsolvable (“Proving P=NP is nontrivial”). The preferred emphatic form is decidedly nontrivial. See trivial, uninteresting, interesting.

"Nontrivial" is also common jargon in other fields of engineering and science, informally highlighting the difficulty of a problem by understating it.

In your example sentence: "This problem is computationally non-trivial".


On a slightly more formal note (but only slightly!), a paragraph from Chapter 6 of James Gleick's Chaos gives an example of a problem like the one you mention:

Using the nonlinear equations of fluid motion, the world’s fastest supercomputers were incapable of accurately tracking a turbulent flow of even a cubic centimeter for more than a few seconds. The blame for this was certainly nature’s more than Landau’s, ... How can all that be going on in that tiny space? Why should it take an infinite amount of logic to figure out what one tiny piece of space/time is going to do?”

This kind of problem can be called "computationally intractable", as FumbleFingers mentioned:

A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice any solution takes too many resources to be useful, is known as an intractable problem. Conversely, a problem that can be solved in practice is called a tractable problem, literally "a problem that can be handled". The term infeasible (literally "cannot be done") is sometimes used interchangeably with intractable, though this risks confusion with a feasible solution in mathematical optimization. (--Wikipedia)

Martin Gardner used several candidates in this excerpt from an essay on the RSA cipher:

These seemingly impossible feats are made possible by what Dime and Hellman call a trapdoor one-way function. Such a function has the following properties: (1) it will change any positive integer x to a unique positive integer y; (2) it has an inverse function that changes y back to x; (3) efficient algorithms exist for computing both the forward function and its inverse: (4) if only the function and its forward algorithm are known, it is computationally infeasible to discover the inverse algorithm.
The last property is the curious one that gives the function its name. It is like a trapdoor: easy to drop through but hard to get up through. (--Mathematical Games, highlights added)

Hard is still used in relation to computation:

It is computationally hard to find two prime factors of a very large number. (--cletus's answer at a plain english explanation of big o notation on Stack Overflow)

After considering Peter Shor's comment that nontrivial is a vast understatement, I found another, more precise word by following links from Wikipedia's article on Computational Complexity:

Transcomputational:

A transcomputational problem is a problem that requires processing of more than {10^{93}} bits of information. The number comes from Earth-scale considerations, but adding less than 30 to the exponent breaks the scale of the known universe. (Transcomputational Problems, Lipton and Regan, an article about Bremermann’s limit)

2
  • 2
    "nontrivial" is no more jargon than "dependent clause" or "couplet" are in grammar and literature. It is used to indicate that, despite superficial simplicity, the solution to a problem needs careful thought. The opprobrious suggestion that it is "swagger" among "common folk" will be rightly resented by some readers.
    – Anton
    Sep 5, 2020 at 18:08
  • 2
    "Nontrivial" may be a vast understatement for the resources required by the problem the OP is describing. Sep 6, 2020 at 16:01
-1

A technical term describing one situation in which this occurs is:

NP Complete

Where NP stands for nondeterministic polynomial time.

In simplistic terms it is used to describe a problem which can be solved by an algorithm which, however, will take an impractical long time to implement as the size of the problem exceeds a low threshold.

4
  • "NP" refers to complexity class both of finding solutions and checking them, and complexity class refers to asymptotic behavior as the input size goes to infinity. A problem can be NP-complete but still solvable in reasonable time for small enough inputs. For instance, mining bitcoin. And a problem can be unfeasible without having a polynomial verification algorithm. Sep 6, 2020 at 2:12
  • 1
    @Acccumulation — Agreed. I did cover your first point in “low threshold”, but should have said that this description related to a particular kind of unfeasibilty. I answered with it as I was surprised the poster didn’t mention it.
    – David
    Sep 6, 2020 at 8:15
  • NP-complete is not going to be understood by people not in computer science or a computer-science adjacent field. And technically, NP-complete applies to problems, and the OP was asking about an adjective to describe methods of solving them. The technical term computer scientists use for describing methods is exponential, which would be a much better answer. Sep 7, 2020 at 14:29
  • @PeterShor The poster did not make it clear to whom he wished to communicate this information. However I agree that he asked for an adjective which my answer does not supply. It does provide information on technical terms, so I'll leave it for posterity, taking the downvotes on the chin. ("Taking one for the team" is the football expression, which must be an answer to another question.) Of course the poster could be told to speak plain English and say that he doesn't have enough computing power to solve the problem, or solving it requires more computing power than he can possibly obtain.
    – David
    Sep 7, 2020 at 15:28

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