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).

Improve this question
$\endgroup$
2
  • $\begingroup$ Have you looked at the Wikipedia talk page? $\endgroup$
    – Yuval Filmus
    Dec 16, 2018 at 8:27
  • $\begingroup$ @YuvalFilmus, I have now. $\endgroup$
    – user626625
    Dec 16, 2018 at 11:13

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\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, 2018 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$
    – John L.
    Dec 18, 2018 at 7:46
  • $\begingroup$ How about cyclomatic complexity? If the number of characters used in a program can be considered as a kind of computational complexity, so could be cyclomatic complexity. $\endgroup$
    – John L.
    Jan 19, 2020 at 18:42
  • $\begingroup$ How about sample complexity that represents the number of training-samples that it needs in order to successfully learn a target function? $\endgroup$
    – John L.
    Feb 4, 2020 at 13:03
  • $\begingroup$ The spacetime complexity should be the most direct example that is more complicated than time complexity and space complexity. $\endgroup$
    – John L.
    Feb 11, 2020 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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