NTIME

http://dbpedia.org/resource/NTIME an entity of type: WikicatComplexityClasses

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. rdf:langString

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 rdf:langString

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). rdf:langString

NTIME(f(n)) とは、計算複雑性理論における複雑性クラスの表現法であり、非決定性チューリング機械を使って O(f(n)) の時間と無制限の空間（領域）を使って解くことが出来る決定問題の集合である。よく知られている複雑性クラス NP は NTIME を使って次のように表現できる。同様に、NEXPTIME クラスも NTIME を使って定義される。非決定性によれば、漸近的により多くの時間をかければ、非決定性機械でより多くの問題を解くことができるとされている。 rdf:langString

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. rdf:langString

在計算複雜性理論裡面，複雜度類NTIME(f(n))是一種可以用非確定型圖靈機使用O(f(n))的時間和無限制的空間所能解決的所有決定性問題的集合。NP這個有名的複雜度類，可以用NTIME來定義如下：相同的，NEXPTIME這個複雜度類是由NTIME定義出來的，非決定型的時間譜系理論說明了非決定型的機器在使用更多時間的前提下可以解決更多的問題。 rdf:langString

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. rdf:langString

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) rdf:langString

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. . rdf:langString

rdfs:label

rdf:langString NTIME (Complexitat)

rdf:langString NTIME

dbpedia-owl:wikiPageID

xsd:integer 658539

dbpedia-owl:wikiPageRevisionID

xsd:integer 1075072050

dbpedia-owl:abstract

rdf:langString 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.

rdf:langString 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.

rdf:langString 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.

rdf:langString 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

rdf:langString 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).

rdf:langString NTIME(f(n)) とは、計算複雑性理論における複雑性クラスの表現法であり、非決定性チューリング機械を使って O(f(n)) の時間と無制限の空間（領域）を使って解くことが出来る決定問題の集合である。よく知られている複雑性クラス NP は NTIME を使って次のように表現できる。同様に、NEXPTIME クラスも NTIME を使って定義される。非決定性によれば、漸近的により多くの時間をかければ、非決定性機械でより多くの問題を解くことができるとされている。

rdf:langString 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.

rdf:langString 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: .

rdf:langString 在計算複雜性理論裡面，複雜度類NTIME(f(n))是一種可以用非確定型圖靈機使用O(f(n))的時間和無限制的空間所能解決的所有決定性問題的集合。NP這個有名的複雜度類，可以用NTIME來定義如下：相同的，NEXPTIME這個複雜度類是由NTIME定義出來的，非決定型的時間譜系理論說明了非決定型的機器在使用更多時間的前提下可以解決更多的問題。

dbpedia-owl:wikiPageLength

xsd:nonNegativeInteger 2414

rdf:type

yago:WikicatComplexityClasses

yago:WikicatComputationalResources

yago:Abstraction100002137

yago:Assets113329641

yago:Class107997703

yago:Collection107951464

yago:Group100031264

yago:Possession100032613

yago:Relation100031921