More complicated resources than time and space complexity

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

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.

• Oracles. How many queries will be answered by an oracle? For example, in quantum query complexity.

• Entropy. How much entropy is needed to run a randomized algorithm or cryptographic algorithm?

• Messages. How many bits are needed to be exchanged so that Alice and Bob can compute a value together?

• Comparisons used in sorting in the comparison sorting model or branching in simple decision tree.

• Memory accesses. How many memory accesses are used in cell probe mode?

• Network bandwidth. This is critical to everyone who is reading this page or using the internet or any network.

• Parallel processes. How many processes are used in the computation?

• Steps of proof. How many steps does it take to prove or refute statements?

• Cache hits. How many cache hits on average will happen when an algorithm runs?

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.

• Characters in source program or bytes in machine code. How long is the source code? I love code golf.

• States. How many states are needed in a finite automaton to describe a regular language? From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity. Or what is the least number of states for a Turing machine to be Turing complete? Small universal Turing machines.

• Boolean circuits. How large or how deep of of Boolean circuits are used to compute boolean functions?

• Non-primitive recursion. When do we need non-primitive recursion to compute large growing functions?

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.

StackExchange Computer Science Q#101622, answer score: 5