"NTIME"@pt . "1075072050"^^ . "In der Komplexit\u00E4tstheorie steht NTIME(f) f\u00FCr die Menge der Sprachen, die von einer nichtdeterministischen Turingmaschine in Zeit O(f) akzeptiert werden k\u00F6nnen. Mittels NTIME werden unter anderem folgende Komplexit\u00E4tsklassen definiert bzw. charakterisiert: \n* 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\u00F6chstens |w| Schritte ben\u00F6tigt. In vorheriger Quelle wird auch gezeigt, dass diese Klasse mit NTIME(n) zusammenf\u00E4llt.) \n* NP:= NTIME(nk) \n* NE:=NTIME(2O(n)) \n* NEXP:= NTIME(2nk)"@de . . "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)) \u2286 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 (Complexitat)"@ca . . . "Na teoria da complexidade computacional, a classe de complexidade NTIME(f(n)) \u00E9 o conjunto dos problemas de decis\u00E3o que podem ser solucionado por uma m\u00E1quina de Turing n\u00E3o-determin\u00EDstica usando um tempo O(f(n)) e espa\u00E7o ilimitado. A classe de complexidade NP pode ser definida em termos de NTIME da seguinte forma: Similarmente, a classe \u00E9 pode ser definida em termos de NTIME da seguinte forma: O n\u00E3o-determin\u00EDstico teorema da hierarquia do tempo diz que m\u00E1quinas n\u00E3o-determin\u00EDsticas podem solucionar mais problemas assintoticamente em mais tempo. NTIME tamb\u00E9m est\u00E1 relacionado com DSPACE da seguinte forma. Para qualquer fun\u00E7\u00E3o de tempo construt\u00EDvel t(n), temos que: ."@pt . . . . . "Na teoria da complexidade computacional, a classe de complexidade NTIME(f(n)) \u00E9 o conjunto dos problemas de decis\u00E3o que podem ser solucionado por uma m\u00E1quina de Turing n\u00E3o-determin\u00EDstica usando um tempo O(f(n)) e espa\u00E7o ilimitado. A classe de complexidade NP pode ser definida em termos de NTIME da seguinte forma: Similarmente, a classe \u00E9 pode ser definida em termos de NTIME da seguinte forma: O n\u00E3o-determin\u00EDstico teorema da hierarquia do tempo diz que m\u00E1quinas n\u00E3o-determin\u00EDsticas podem solucionar mais problemas assintoticamente em mais tempo. ."@pt . . "NTIME"@de . "NTIME(f(n)) \u3068\u306F\u3001\u8A08\u7B97\u8907\u96D1\u6027\u7406\u8AD6\u306B\u304A\u3051\u308B\u8907\u96D1\u6027\u30AF\u30E9\u30B9\u306E\u8868\u73FE\u6CD5\u3067\u3042\u308A\u3001\u975E\u6C7A\u5B9A\u6027\u30C1\u30E5\u30FC\u30EA\u30F3\u30B0\u6A5F\u68B0\u3092\u4F7F\u3063\u3066 O(f(n)) \u306E\u6642\u9593\u3068\u7121\u5236\u9650\u306E\u7A7A\u9593\uFF08\u9818\u57DF\uFF09\u3092\u4F7F\u3063\u3066\u89E3\u304F\u3053\u3068\u304C\u51FA\u6765\u308B\u6C7A\u5B9A\u554F\u984C\u306E\u96C6\u5408\u3067\u3042\u308B\u3002 \u3088\u304F\u77E5\u3089\u308C\u3066\u3044\u308B\u8907\u96D1\u6027\u30AF\u30E9\u30B9 NP \u306F NTIME \u3092\u4F7F\u3063\u3066\u6B21\u306E\u3088\u3046\u306B\u8868\u73FE\u3067\u304D\u308B\u3002 \u540C\u69D8\u306B\u3001NEXPTIME \u30AF\u30E9\u30B9\u3082 NTIME \u3092\u4F7F\u3063\u3066\u5B9A\u7FA9\u3055\u308C\u308B\u3002\u975E\u6C7A\u5B9A\u6027\u306B\u3088\u308C\u3070\u3001\u6F38\u8FD1\u7684\u306B\u3088\u308A\u591A\u304F\u306E\u6642\u9593\u3092\u304B\u3051\u308C\u3070\u3001\u975E\u6C7A\u5B9A\u6027\u6A5F\u68B0\u3067\u3088\u308A\u591A\u304F\u306E\u554F\u984C\u3092\u89E3\u304F\u3053\u3068\u304C\u3067\u304D\u308B\u3068\u3055\u308C\u3066\u3044\u308B\u3002"@ja . . "En th\u00E9orie de la complexit\u00E9, NTIME d\u00E9signe une famille de classes de complexit\u00E9 caract\u00E9ris\u00E9e par leur complexit\u00E9 en temps sur une machine de Turing non d\u00E9terministe. Plus pr\u00E9cis\u00E9ment, est la classe des probl\u00E8mes de d\u00E9cision qui, pour une entr\u00E9e de taille , peuvent \u00EAtre r\u00E9solus en temps par une machine de Turing non d\u00E9terministe."@fr . . . . . "2414"^^ . . . . "658539"^^ . . . . . . . . . "NTIME"@zh . . "NTIME"@fr . . "NTIME"@nl . "\u5728\u8A08\u7B97\u8907\u96DC\u6027\u7406\u8AD6\u88E1\u9762\uFF0C\u8907\u96DC\u5EA6\u985ENTIME(f(n))\u662F\u4E00\u7A2E\u53EF\u4EE5\u7528\u975E\u78BA\u5B9A\u578B\u5716\u9748\u6A5F\u4F7F\u7528O(f(n))\u7684\u6642\u9593\u548C\u7121\u9650\u5236\u7684\u7A7A\u9593\u6240\u80FD\u89E3\u6C7A\u7684\u6240\u6709\u6C7A\u5B9A\u6027\u554F\u984C\u7684\u96C6\u5408\u3002NP\u9019\u500B\u6709\u540D\u7684\u8907\u96DC\u5EA6\u985E\uFF0C\u53EF\u4EE5\u7528NTIME\u4F86\u5B9A\u7FA9\u5982\u4E0B\uFF1A \u76F8\u540C\u7684\uFF0CNEXPTIME\u9019\u500B\u8907\u96DC\u5EA6\u985E\u662F\u7531NTIME\u5B9A\u7FA9\u51FA\u4F86\u7684\uFF0C\u975E\u6C7A\u5B9A\u578B\u7684\u6642\u9593\u8B5C\u7CFB\u7406\u8AD6\u8AAA\u660E\u4E86\u975E\u6C7A\u5B9A\u578B\u7684\u6A5F\u5668\u5728\u4F7F\u7528\u66F4\u591A\u6642\u9593\u7684\u524D\u63D0\u4E0B\u53EF\u4EE5\u89E3\u6C7A\u66F4\u591A\u7684\u554F\u984C\u3002"@zh . "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 . "En teoria de la complexitat, la classe de complexitat NTIME(f(n)) \u00E9s la classe dels problemes de decisi\u00F3 que es poden resoldre per una m\u00E0quina de Turing no determinista en un temps O(f(n)), on O \u00E9s la notaci\u00F3 de O gran, f \u00E9s una funci\u00F3 qualsevol i n \u00E9s la mida de l'entrada. Aix\u00F2 vol dir que pel problema donat, una m\u00E0quina de Turing no determinista per una entrada de mida n funcionar\u00E0 un temps O(f(n)) i sempre s'aturar\u00E0 i acceptar\u00E0 o rebutjar\u00E0 l'entrada."@ca . "NTIME"@ja . . "In der Komplexit\u00E4tstheorie steht NTIME(f) f\u00FCr die Menge der Sprachen, die von einer nichtdeterministischen Turingmaschine in Zeit O(f) akzeptiert werden k\u00F6nnen. Mittels NTIME werden unter anderem folgende Komplexit\u00E4tsklassen definiert bzw. charakterisiert: \n* 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\u00F6chstens |w| Schritte ben\u00F6tigt. In vorheriger Quelle wird auch gezeigt, dass diese Klasse mit NTIME(n) zusammenf\u00E4llt.) \n* NP:= NTIME(nk) \n* NE:=NTIME(2O(n)) \n* NEXP:= NTIME(2nk) Mittels Diagonalisierung l\u00E4sst sich zeigen, dass die Teilmengenbeziehung in der Hierarchie Q \u2282 NP \u2282 NE \u2282 NEXP echt sind."@de . . "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)) \u2286 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 . . "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)) \u3068\u306F\u3001\u8A08\u7B97\u8907\u96D1\u6027\u7406\u8AD6\u306B\u304A\u3051\u308B\u8907\u96D1\u6027\u30AF\u30E9\u30B9\u306E\u8868\u73FE\u6CD5\u3067\u3042\u308A\u3001\u975E\u6C7A\u5B9A\u6027\u30C1\u30E5\u30FC\u30EA\u30F3\u30B0\u6A5F\u68B0\u3092\u4F7F\u3063\u3066 O(f(n)) \u306E\u6642\u9593\u3068\u7121\u5236\u9650\u306E\u7A7A\u9593\uFF08\u9818\u57DF\uFF09\u3092\u4F7F\u3063\u3066\u89E3\u304F\u3053\u3068\u304C\u51FA\u6765\u308B\u6C7A\u5B9A\u554F\u984C\u306E\u96C6\u5408\u3067\u3042\u308B\u3002 \u3088\u304F\u77E5\u3089\u308C\u3066\u3044\u308B\u8907\u96D1\u6027\u30AF\u30E9\u30B9 NP \u306F NTIME \u3092\u4F7F\u3063\u3066\u6B21\u306E\u3088\u3046\u306B\u8868\u73FE\u3067\u304D\u308B\u3002 \u540C\u69D8\u306B\u3001NEXPTIME \u30AF\u30E9\u30B9\u3082 NTIME \u3092\u4F7F\u3063\u3066\u5B9A\u7FA9\u3055\u308C\u308B\u3002\u975E\u6C7A\u5B9A\u6027\u306B\u3088\u308C\u3070\u3001\u6F38\u8FD1\u7684\u306B\u3088\u308A\u591A\u304F\u306E\u6642\u9593\u3092\u304B\u3051\u308C\u3070\u3001\u975E\u6C7A\u5B9A\u6027\u6A5F\u68B0\u3067\u3088\u308A\u591A\u304F\u306E\u554F\u984C\u3092\u89E3\u304F\u3053\u3068\u304C\u3067\u304D\u308B\u3068\u3055\u308C\u3066\u3044\u308B\u3002"@ja . . "\u5728\u8A08\u7B97\u8907\u96DC\u6027\u7406\u8AD6\u88E1\u9762\uFF0C\u8907\u96DC\u5EA6\u985ENTIME(f(n))\u662F\u4E00\u7A2E\u53EF\u4EE5\u7528\u975E\u78BA\u5B9A\u578B\u5716\u9748\u6A5F\u4F7F\u7528O(f(n))\u7684\u6642\u9593\u548C\u7121\u9650\u5236\u7684\u7A7A\u9593\u6240\u80FD\u89E3\u6C7A\u7684\u6240\u6709\u6C7A\u5B9A\u6027\u554F\u984C\u7684\u96C6\u5408\u3002NP\u9019\u500B\u6709\u540D\u7684\u8907\u96DC\u5EA6\u985E\uFF0C\u53EF\u4EE5\u7528NTIME\u4F86\u5B9A\u7FA9\u5982\u4E0B\uFF1A \u76F8\u540C\u7684\uFF0CNEXPTIME\u9019\u500B\u8907\u96DC\u5EA6\u985E\u662F\u7531NTIME\u5B9A\u7FA9\u51FA\u4F86\u7684\uFF0C\u975E\u6C7A\u5B9A\u578B\u7684\u6642\u9593\u8B5C\u7CFB\u7406\u8AD6\u8AAA\u660E\u4E86\u975E\u6C7A\u5B9A\u578B\u7684\u6A5F\u5668\u5728\u4F7F\u7528\u66F4\u591A\u6642\u9593\u7684\u524D\u63D0\u4E0B\u53EF\u4EE5\u89E3\u6C7A\u66F4\u591A\u7684\u554F\u984C\u3002"@zh . . . . . "NTIME"@en . "En th\u00E9orie de la complexit\u00E9, NTIME d\u00E9signe une famille de classes de complexit\u00E9 caract\u00E9ris\u00E9e par leur complexit\u00E9 en temps sur une machine de Turing non d\u00E9terministe. Plus pr\u00E9cis\u00E9ment, est la classe des probl\u00E8mes de d\u00E9cision qui, pour une entr\u00E9e de taille , peuvent \u00EAtre r\u00E9solus en temps par une machine de Turing non d\u00E9terministe."@fr . "En teoria de la complexitat, la classe de complexitat NTIME(f(n)) \u00E9s la classe dels problemes de decisi\u00F3 que es poden resoldre per una m\u00E0quina de Turing no determinista en un temps O(f(n)), on O \u00E9s la notaci\u00F3 de O gran, f \u00E9s una funci\u00F3 qualsevol i n \u00E9s la mida de l'entrada. Aix\u00F2 vol dir que pel problema donat, una m\u00E0quina de Turing no determinista per una entrada de mida n funcionar\u00E0 un temps O(f(n)) i sempre s'aturar\u00E0 i acceptar\u00E0 o rebutjar\u00E0 l'entrada. L'espai disponible per la m\u00E0quina no est\u00E0 limitat, tot i que no pot sobrepassar O(f(n)), ja que el temps disponible limita l'espai que es pot utilitzar."@ca . . "En teor\u00EDa de la complejidad computacional, la clase de complejidad NTIME(f(n)) es el conjunto de los problemas de decisi\u00F3n que pueden ser resueltos en una m\u00E1quina de Turing no determinista en tiempo O(f(n)) y espacio ilimitado. La clase de complejidad NP se puede definir en t\u00E9rminos de NTIME como: \n* Datos: Q1933581"@es . . "NTIME"@es . . . . . . "En teor\u00EDa de la complejidad computacional, la clase de complejidad NTIME(f(n)) es el conjunto de los problemas de decisi\u00F3n que pueden ser resueltos en una m\u00E1quina de Turing no determinista en tiempo O(f(n)) y espacio ilimitado. La clase de complejidad NP se puede definir en t\u00E9rminos de NTIME como: \n* Datos: Q1933581"@es . . .