In computational complexity theory, the complexity class NTIME(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine which runs in time O(f(n)). Here O is the big O notation, f is some function, and n is the size of the input (for which the problem is to be decided).
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - NTIME (Complexitat) (ca)
- NTIME (de)
- NTIME (es)
- NTIME (fr)
- NTIME (ja)
- NTIME (en)
- NTIME (nl)
- NTIME (pt)
- NTIME (zh)
|
| rdfs:comment
| - En théorie de la complexité, NTIME désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing non 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 non déterministe. (fr)
- En teoría de la complejidad computacional, la clase de complejidad NTIME(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en tiempo O(f(n)) y espacio ilimitado. La clase de complejidad NP se puede definir en términos de NTIME como:
* Datos: Q1933581 (es)
- In computational complexity theory, the complexity class NTIME(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine which runs in time O(f(n)). Here O is the big O notation, f is some function, and n is the size of the input (for which the problem is to be decided). (en)
- NTIME(f(n)) とは、計算複雑性理論における複雑性クラスの表現法であり、非決定性チューリング機械を使って O(f(n)) の時間と無制限の空間（領域）を使って解くことが出来る決定問題の集合である。 よく知られている複雑性クラス NP は NTIME を使って次のように表現できる。 同様に、NEXPTIME クラスも NTIME を使って定義される。非決定性によれば、漸近的により多くの時間をかければ、非決定性機械でより多くの問題を解くことができるとされている。 (ja)
- In de complexiteitstheorie is NTIME( f(n) ) een die alle beslissingsproblemen bevat die in O(f(n)) opgelost kunnen worden door een niet-deterministische turingmachine. Veel bekende complexiteitsklassen kunnen gedefinieerd worden in termen van NTIME. Zo kan NP gedefinieerd worden als en als . In verhouding tot DTIME 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)
- 在計算複雜性理論裡面，複雜度類NTIME(f(n))是一種可以用非確定型圖靈機使用O(f(n))的時間和無限制的空間所能解決的所有決定性問題的集合。NP這個有名的複雜度類，可以用NTIME來定義如下： 相同的，NEXPTIME這個複雜度類是由NTIME定義出來的，非決定型的時間譜系理論說明了非決定型的機器在使用更多時間的前提下可以解決更多的問題。 (zh)
- En teoria de la complexitat, la classe de complexitat NTIME(f(n)) és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing no determinista en un temps O(f(n)), on O és la notació de O gran, f és una funció qualsevol i n és la mida de l'entrada. Això vol dir que pel problema donat, una màquina de Turing no determinista per una entrada de mida n funcionarà un temps O(f(n)) i sempre s'aturarà i acceptarà o rebutjarà l'entrada. (ca)
- In der Komplexitätstheorie steht NTIME(f) für die Menge der Sprachen, die von einer nichtdeterministischen Turingmaschine in Zeit O(f) akzeptiert werden können. Mittels NTIME werden unter anderem folgende Komplexitätsklassen definiert bzw. charakterisiert:
* Q=NTIME(n) (Formal wird Q als Familie aller Sprachen L mit L=L(M) definiert, wobei jede Berechnung von M auf Eingabe w höchstens |w| Schritte benötigt. In vorheriger Quelle wird auch gezeigt, dass diese Klasse mit NTIME(n) zusammenfällt.)
* NP:= NTIME(nk)
* NE:=NTIME(2O(n))
* NEXP:= NTIME(2nk) (de)
- Na teoria da complexidade computacional, a classe de complexidade NTIME(f(n)) é o conjunto dos problemas de decisão que podem ser solucionado por uma máquina de Turing não-determinística usando um tempo O(f(n)) e espaço ilimitado. A classe de complexidade NP pode ser definida em termos de NTIME da seguinte forma: Similarmente, a classe é pode ser definida em termos de NTIME da seguinte forma: O não-determinístico teorema da hierarquia do tempo diz que máquinas não-determinísticas podem solucionar mais problemas assintoticamente em mais tempo. . (pt)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - En teoria de la complexitat, la classe de complexitat NTIME(f(n)) és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing no determinista en un temps O(f(n)), on O és la notació de O gran, f és una funció qualsevol i n és la mida de l'entrada. Això vol dir que pel problema donat, una màquina de Turing no determinista per una entrada de mida n funcionarà un temps O(f(n)) i sempre s'aturarà i acceptarà o rebutjarà l'entrada. L'espai disponible per la màquina no està limitat, tot i que no pot sobrepassar O(f(n)), ja que el temps disponible limita l'espai que es pot utilitzar. (ca)
- In der Komplexitätstheorie steht NTIME(f) für die Menge der Sprachen, die von einer nichtdeterministischen Turingmaschine in Zeit O(f) akzeptiert werden können. Mittels NTIME werden unter anderem folgende Komplexitätsklassen definiert bzw. charakterisiert:
* Q=NTIME(n) (Formal wird Q als Familie aller Sprachen L mit L=L(M) definiert, wobei jede Berechnung von M auf Eingabe w höchstens |w| Schritte benötigt. In vorheriger Quelle wird auch gezeigt, dass diese Klasse mit NTIME(n) zusammenfällt.)
* NP:= NTIME(nk)
* NE:=NTIME(2O(n))
* NEXP:= NTIME(2nk) Mittels Diagonalisierung lässt sich zeigen, dass die Teilmengenbeziehung in der Hierarchie Q ⊂ NP ⊂ NE ⊂ NEXP echt sind. (de)
- En théorie de la complexité, NTIME désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing non 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 non déterministe. (fr)
- En teoría de la complejidad computacional, la clase de complejidad NTIME(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en tiempo O(f(n)) y espacio ilimitado. La clase de complejidad NP se puede definir en términos de NTIME como:
* Datos: Q1933581 (es)
- In computational complexity theory, the complexity class NTIME(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine which runs in time O(f(n)). Here O is the big O notation, f is some function, and n is the size of the input (for which the problem is to be decided). (en)
- NTIME(f(n)) とは、計算複雑性理論における複雑性クラスの表現法であり、非決定性チューリング機械を使って O(f(n)) の時間と無制限の空間（領域）を使って解くことが出来る決定問題の集合である。 よく知られている複雑性クラス NP は NTIME を使って次のように表現できる。 同様に、NEXPTIME クラスも NTIME を使って定義される。非決定性によれば、漸近的により多くの時間をかければ、非決定性機械でより多くの問題を解くことができるとされている。 (ja)
- In de complexiteitstheorie is NTIME( f(n) ) een die alle beslissingsproblemen bevat die in O(f(n)) opgelost kunnen worden door een niet-deterministische turingmachine. Veel bekende complexiteitsklassen kunnen gedefinieerd worden in termen van NTIME. Zo kan NP gedefinieerd worden als en als . In verhouding tot DTIME 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)
- Na teoria da complexidade computacional, a classe de complexidade NTIME(f(n)) é o conjunto dos problemas de decisão que podem ser solucionado por uma máquina de Turing não-determinística usando um tempo O(f(n)) e espaço ilimitado. A classe de complexidade NP pode ser definida em termos de NTIME da seguinte forma: Similarmente, a classe é pode ser definida em termos de NTIME da seguinte forma: O não-determinístico teorema da hierarquia do tempo diz que máquinas não-determinísticas podem solucionar mais problemas assintoticamente em mais tempo. NTIME também está relacionado com DSPACE da seguinte forma. Para qualquer função de tempo construtível t(n), temos que: . (pt)
- 在計算複雜性理論裡面，複雜度類NTIME(f(n))是一種可以用非確定型圖靈機使用O(f(n))的時間和無限制的空間所能解決的所有決定性問題的集合。NP這個有名的複雜度類，可以用NTIME來定義如下： 相同的，NEXPTIME這個複雜度類是由NTIME定義出來的，非決定型的時間譜系理論說明了非決定型的機器在使用更多時間的前提下可以解決更多的問題。 (zh)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
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)