4
$\begingroup$

The wikipedia page on computational resources states that there are many different resources that have been defined:

In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.

The simplest computational resources are computation time, the number of steps necessary to solve a problem, and memory space, the amount of storage needed while solving the problem, but many more complicated resources have been defined.[citation needed]

Unfortunately, this claim doesn't have a citation.

What are these more complicated resources that have been defined?

  • I can imagine something like parallel processes used?

  • the wikipedia talk page talks about communication bandwidth: e.g. network bandwidth, and memory busses. ( this seems fairly "processor-dependent"? Not sure if there is a theoretical analysis of this).

$\endgroup$
  • $\begingroup$ "parallel processing complexity"? Complexity is not a resource. Complexity is about the measurement of how much is needed or how difficult to run an algorithm. It looks like you meant "parallel processes used" $\endgroup$ – Apass.Jack Dec 16 '18 at 7:25
  • $\begingroup$ @Apass.Jack, thank you for the correction. $\endgroup$ – user626625 Dec 16 '18 at 7:49
  • $\begingroup$ Have you looked at the Wikipedia talk page? $\endgroup$ – Yuval Filmus Dec 16 '18 at 8:27
  • $\begingroup$ @YuvalFilmus, I have now. $\endgroup$ – user626625 Dec 16 '18 at 11:13
5
$\begingroup$

It is interesting that claim, "many more complicated resources have been defined" has been present since the very first version of that Wikipedia page created in 2006, whose accompanying comment is "start article (will have to finish later, lightning storm)". That page is created by Wikipedia user Creidieki. That claim has never been explained on that page.

What are these more complicated resources that have been defined?

Here are some computation resources that may or may not be more complicated. Some of them may seen as variations of the computation time and memory space.

We could also think of some more outlandish ones. How can we measure the complexity of lambda calculus reasonably? Could priority be considered as computation resource as well?

In addition to the resources that are needed to run algorithms to solve problems, We can also examine the resources or even techniques that are needed to build the computation machines.

In summary, we can check the list of complexity classes in Wikipedia or Complexity Zoo to find various computation resources that are considered in complexity analysis. Hopefully, this answer have given you a rough idea how diverse and interesting the computation resources and the complexity classes are.

$\endgroup$
  • $\begingroup$ interesting! I will look at the complexity zoo as well. One particular example that seems interesting which I don't understand is your "entropy" example. Why would you "need a particular amount of entropy" to run a randomized algorithm? $\endgroup$ – user626625 Dec 18 '18 at 7:24
  • $\begingroup$ If there is not enough entropy, then a randomized algorithm might not be correct. For example, an algorithm is required to generate a random permutation to be used in statistical testing. Some randomized algorithms takes advantage of randomness to improve its expected efficiency. You may want to check derandomization. $\endgroup$ – Apass.Jack Dec 18 '18 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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