Im Allgemeinen sprechen wir bei der Komplexität der Berechnungen von Zeit- und Raumkomplexität. Das heißt, wir überlegen uns, wie viel Zeit oder Platz für die Lösung eines Problems benötigt wird.Andere Ressourcen jenseits von Zeit und Raum in Rechenkomplexität
Ich würde gerne wissen, ob es eine andere Art von Ressource (jenseits von Zeit und Raum) gibt, dass wir eine Referenz für die Diskussion der computacional Komplexität verwenden könnten.
Leute haben die Anzahl der Verweise auf externen Speicher (https://www.ittc.ku.edu/~jsv/Papers/Vit.IO_book.pdf) und die Verwendung von Cache-Speicher (https://en.wikipedia.org/wiki/Cache-oblivious_algorithm) berücksichtigt. Wenn die Berechnungen zwischen zwei oder mehr Knoten aufgeteilt sind, ist die Komplexität der Kommunikation zwischen diesen Knoten von Interesse (https://en.wikipedia.org/wiki/Communication_complexity) und es gibt einige nette Beweise hier.
Es gibt auch Verbindungen zwischen diesen Maßnahmen. Am offensichtlichsten ist, dass die Verwendung fast jeder Ressource Zeit benötigt, so dass alles, was nicht länger als T Zeiteinheiten dauert, wahrscheinlich nicht mehr als O (T) -Einheiten irgendeiner anderen Ressource benötigt. Es gibt ein Papier "Ein Überblick über die Theorie der Computational Complexity" von Hartmanis und Hopcroft, das rechnerische Komplexität auf eine feste mathematische Grundlage stellt. Dies definiert eine sehr allgemeine Vorstellung von Berechnungskomplexitätsmaßen und (Theorem 4) beweist, dass (ihre Zusammenfassung) "eine Funktion, die in einem Maß" einfach "zu berechnen ist," einfach "in anderen Maßen zu berechnen ist". Jedoch ist dieses Ergebnis (wie der Rest des Artikels) in mathematisch abstrakten Begriffen, die in der realen Welt keine praktische Konsequenz haben. Die Verbindung zwischen den beiden hier verwendeten Komplexitäten ist so locker, dass es durchaus möglich ist, dass die Polynomkomplexität in einem Maß exponentielle Komplexität (oder schlechter) in dem anderen Maß sein könnte.
Während ich sie nicht im Rahmen der Komplexitätstheorie diskutiert habe, sind andere Eigenschaften einer Berechnung jenseits von Raum und Zeit (Latenz), die man untersuchen möchte, _throughput_ und _energy consumption_. Die Möglichkeit, Teilergebnisse frühzeitig zu produzieren, könnte interessant sein, sodass die Latenz zu einem kritischen ersten Ergebnis getrennt von der Latenzzeit bis zum vollen Ergebnis untersucht werden kann. –