In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm. It is one of the most well-studied complexity resources, because it corresponds so closely to an important real-world resource (the amount of time it takes a computer to solve a problem).
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - DTIME (Complexitat) (ca)
- DTIME (de)
- DTIME (es)
- DTIME (en)
- DTIME (fr)
- DTIME (ja)
- DTIME (pl)
- DTIME (nl)
- Dtime (pt)
- DTIME (zh)
|
| rdfs:comment
| - En teoría de la complejidad computacional, la clase de complejidad DTIME(f(n)) (también llamada TIME(f(n))) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(f(n)), y espacio ilimitado. La clase de complejidad P se puede definir a partir de DTIME como:
* Datos: Q1155831 (es)
- En théorie de la complexité, DTIME (ou TIME) désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing déterministe. Plus précisément, est la classe des problèmes de décision qui, pour une entrée de taille , peuvent être résolus en temps par une machine de Turing déterministe. (fr)
- DTIME（またはTIME）は、計算複雑性理論における決定性チューリング機械での計算時間という計算資源を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要する時間の量（ステップ数）を表す。実際のリソース（プログラムの実行にかかる時間）と直接対応することから、最もよく研究されている計算資源の1つである。 DTIMEという資源は複雑性クラスの定義に使われる。複雑性クラスとは、ある特定の計算時間量で解ける全ての決定問題の集合である。入力長 の問題を解くのに の計算時間がかかる場合、その複雑性クラスは （または ）となる。このとき使用するメモリ空間量に制限はないが、他の複雑性尺度は制限されることもある。 (ja)
- In de complexiteitstheorie is DTIME(f(n)), ook bekend als TIME(f(n)), een die alle beslissingsproblemen bevat die in O(f(n)) tijd opgelost kunnen worden door een deterministische turingmachine. Veel bekende complexiteitsklassen kunnen gedefinieerd worden in termen van DTIME. Zo kan P gedefinieerd worden als en als . In verhouding tot NTIME geldt dat DTIME(f(n)) ⊆ NTIME(f(n)) voor elke functie f(n) aangezien de benodigde tijd op een niet-deterministische turingmachine die geen niet-determinisme gebruikt gelijk is aan een deterministische turingmachine. (nl)
- 在計算複雜度理論內，DTIME（或者TIME）是一個圖靈機的計算資源或者計算時間的計量方式。它代表一個"普通"有實體的電腦解決特定，使用特定演算法，所要花費的時間。這個計算資源是最被廣泛研究的計算資源，因為它與真實世界所重視的資源（要花費多少時間才能計算出一個問題）息息相關。 DTIME這個資源常被使用來定義複雜度類，亦即，可以在特定時間內解決的決定性問題其集合。如果一個問題其輸入的大小為n，並且可要求f(n)的計算時間來解決，那我們說這問題在DTIME(f(n))（or TIME(f(n))）裡面。這裡沒有限制必須使用多少記憶體空間（參見計算資源），但是有可能會限制一些其他的計算資源（像是可否使用交替圖靈機）。 (zh)
- En la Teoria de complexitat computacional, la família DTIME (de vegades simplement TIME) és el recurs de computació en temps de computació per una màquina de Turing determinista. Representa la quantitat de temps (o nombre de cicles de computació) que un computador "normal" prendrà per resoldre un cert problema computacional usant un cert algorisme. És un dels recursos més ben estudiats perquè es correspon amb un recurs real força important com és el temps de còmput. (ca)
- In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm. It is one of the most well-studied complexity resources, because it corresponds so closely to an important real-world resource (the amount of time it takes a computer to solve a problem). (en)
- In der Komplexitätstheorie steht DTIME(f) oder auch kurz TIME(f) für die Menge der Zeitkomplexitätsklassen in Bezug auf eine deterministische Turingmaschine. Wird eine konkrete Funktion f angegeben, so bedeutet dies: DTIME(f) ist die Klasse derjenigen Entscheidungsprobleme, die auf einer deterministischen Turingmaschine in O(f) Zeit lösbar sind. Man beachte, dass bei Angabe einer konkreten Funktion f die Bezeichnung DTIME(f) für eine einzelne Komplexitätsklasse steht, während bei Verwendung einer nicht näher definierten Funktion f die Bezeichnung DTIME(f) eine ganze Menge von Komplexitätsklassen bezeichnet. Darüber hinaus sieht man in der Regel von konstanten Faktoren bei der Funktionsdefinition von f ab und setzt somit DTIME(f) = DTIME(O(f)). Die Rechtfertigung für diese Vorgehensweise li (de)
- W teorii złożoności obliczeniowej DTIME jest klasą złożoności czasowej dla deterministycznej maszyny Turinga. Reprezentuje czas (lub liczbę kroków obliczeniowych), jaki „normalny” komputer poświęciłby na rozwiązanie określonego problemu obliczeniowego przy użyciu określonego algorytmu. Jest to jedna z najlepiej zbadanych klas złożoności, ponieważ ściśle odpowiada ważnemu zasobom w świecie rzeczywistym (ilości czasu potrzebnego komputerowi na rozwiązanie problemu). (pl)
- Na teoria da complexidade computacional, DTIME (ou TIME) é o recurso computacional de tempo de computação para uma máquina de Turing determinística. Ela representa a quantidade de tempo (ou número de passos de cálculo) que um computador "normal" físico seria necessário para resolver um determinado problema computacional usando um certo algoritmo. É um dos mais bem estudado recursos complexidade, porque corresponde tão intimamente a um recurso importante do mundo real (a quantidade de tempo que leva um computador para resolver um problema). (pt)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - En la Teoria de complexitat computacional, la família DTIME (de vegades simplement TIME) és el recurs de computació en temps de computació per una màquina de Turing determinista. Representa la quantitat de temps (o nombre de cicles de computació) que un computador "normal" prendrà per resoldre un cert problema computacional usant un cert algorisme. És un dels recursos més ben estudiats perquè es correspon amb un recurs real força important com és el temps de còmput. Aquest recurs s'utilitza per definir classes de complexitat, conjunts de problemes de decisió que es poden resoldre usant un cert temps de computació. Si un problema amb una entrada de mida n es pot solucionar en O(f(n)), es te la classe de complexitat DTIME(f(n)). No hi ha restricció en la quantitat de memòria utilitzada, però pot haver-hi restriccions en d'altres recursos. (ca)
- In der Komplexitätstheorie steht DTIME(f) oder auch kurz TIME(f) für die Menge der Zeitkomplexitätsklassen in Bezug auf eine deterministische Turingmaschine. Wird eine konkrete Funktion f angegeben, so bedeutet dies: DTIME(f) ist die Klasse derjenigen Entscheidungsprobleme, die auf einer deterministischen Turingmaschine in O(f) Zeit lösbar sind. Man beachte, dass bei Angabe einer konkreten Funktion f die Bezeichnung DTIME(f) für eine einzelne Komplexitätsklasse steht, während bei Verwendung einer nicht näher definierten Funktion f die Bezeichnung DTIME(f) eine ganze Menge von Komplexitätsklassen bezeichnet. Darüber hinaus sieht man in der Regel von konstanten Faktoren bei der Funktionsdefinition von f ab und setzt somit DTIME(f) = DTIME(O(f)). Die Rechtfertigung für diese Vorgehensweise liefert u. a. das lineare Speedup-Theorem. Man verwendet die Schreibweise DTIME(f) für alle Zeitklassen, die keinen eigenen Namen haben, so etwa im Rahmen der Zeithierarchiesätze. Darüber hinaus kann man sie zur Definition konkreterer Komplexitätsklassen einsetzen: So ist beispielsweise die wichtige Klasse P wie folgt definiert: . (de)
- In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm. It is one of the most well-studied complexity resources, because it corresponds so closely to an important real-world resource (the amount of time it takes a computer to solve a problem). The resource DTIME is used to define complexity classes, sets of all of the decision problems which can be solved using a certain amount of computation time. If a problem of input size n can be solved in , we have a complexity class (or ). There is no restriction on the amount of memory space used, but there may be restrictions on some other complexity resources (like alternation). (en)
- En teoría de la complejidad computacional, la clase de complejidad DTIME(f(n)) (también llamada TIME(f(n))) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(f(n)), y espacio ilimitado. La clase de complejidad P se puede definir a partir de DTIME como:
* Datos: Q1155831 (es)
- En théorie de la complexité, DTIME (ou TIME) désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing déterministe. Plus précisément, est la classe des problèmes de décision qui, pour une entrée de taille , peuvent être résolus en temps par une machine de Turing déterministe. (fr)
- DTIME（またはTIME）は、計算複雑性理論における決定性チューリング機械での計算時間という計算資源を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要する時間の量（ステップ数）を表す。実際のリソース（プログラムの実行にかかる時間）と直接対応することから、最もよく研究されている計算資源の1つである。 DTIMEという資源は複雑性クラスの定義に使われる。複雑性クラスとは、ある特定の計算時間量で解ける全ての決定問題の集合である。入力長 の問題を解くのに の計算時間がかかる場合、その複雑性クラスは （または ）となる。このとき使用するメモリ空間量に制限はないが、他の複雑性尺度は制限されることもある。 (ja)
- In de complexiteitstheorie is DTIME(f(n)), ook bekend als TIME(f(n)), een die alle beslissingsproblemen bevat die in O(f(n)) tijd opgelost kunnen worden door een deterministische turingmachine. Veel bekende complexiteitsklassen kunnen gedefinieerd worden in termen van DTIME. Zo kan P gedefinieerd worden als en als . In verhouding tot NTIME geldt dat DTIME(f(n)) ⊆ NTIME(f(n)) voor elke functie f(n) aangezien de benodigde tijd op een niet-deterministische turingmachine die geen niet-determinisme gebruikt gelijk is aan een deterministische turingmachine. (nl)
- W teorii złożoności obliczeniowej DTIME jest klasą złożoności czasowej dla deterministycznej maszyny Turinga. Reprezentuje czas (lub liczbę kroków obliczeniowych), jaki „normalny” komputer poświęciłby na rozwiązanie określonego problemu obliczeniowego przy użyciu określonego algorytmu. Jest to jedna z najlepiej zbadanych klas złożoności, ponieważ ściśle odpowiada ważnemu zasobom w świecie rzeczywistym (ilości czasu potrzebnego komputerowi na rozwiązanie problemu). Zasób DTIME służy do definiowania klas złożoności, zestawów wszystkich problemów decyzyjnych, które można rozwiązać za pomocą określonego czasu obliczeniowego. Jeśli problem rozmiaru wejściowego n można rozwiązać w mamy klasę złożoności (lub ). Nie ma ograniczeń co do ilości używanej pamięci, ale mogą istnieć ograniczenia dotyczące niektórych innych zasobów złożoności (takich jak przemienność). (pl)
- Na teoria da complexidade computacional, DTIME (ou TIME) é o recurso computacional de tempo de computação para uma máquina de Turing determinística. Ela representa a quantidade de tempo (ou número de passos de cálculo) que um computador "normal" físico seria necessário para resolver um determinado problema computacional usando um certo algoritmo. É um dos mais bem estudado recursos complexidade, porque corresponde tão intimamente a um recurso importante do mundo real (a quantidade de tempo que leva um computador para resolver um problema). O recurso DTIME é usado para definir classes de complexidade, conjuntos de todos os problemas de decisão que podem ser resolvidos usando uma certa quantidade de tempo de computação. Se um problema de tamanho da entrada n pode exigir tempo de computação f (n) para resolver, temos uma classe de complexidade DTIME (f (n)) (ou TIME (f (n))). Não há nenhuma restrição sobre a quantidade de espaço de memória usado, mas pode haver restrições em alguns outros recursos de complexidade (como alternância). (pt)
- 在計算複雜度理論內，DTIME（或者TIME）是一個圖靈機的計算資源或者計算時間的計量方式。它代表一個"普通"有實體的電腦解決特定，使用特定演算法，所要花費的時間。這個計算資源是最被廣泛研究的計算資源，因為它與真實世界所重視的資源（要花費多少時間才能計算出一個問題）息息相關。 DTIME這個資源常被使用來定義複雜度類，亦即，可以在特定時間內解決的決定性問題其集合。如果一個問題其輸入的大小為n，並且可要求f(n)的計算時間來解決，那我們說這問題在DTIME(f(n))（or TIME(f(n))）裡面。這裡沒有限制必須使用多少記憶體空間（參見計算資源），但是有可能會限制一些其他的計算資源（像是可否使用交替圖靈機）。 (zh)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)