NEXPTIME
http://dbpedia.org/resource/NEXPTIME an entity of type: WikicatComplexityClasses
En teoría de la complejidad computacional, la clase de complejidad NEXPTIME es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en tiempo O(2p(n)), donde p(n) es una función polinomial sobre n. En función de NTIME,
* Datos: Q1575791
rdf:langString
In der Komplexitätstheorie steht NEXPTIME (manchmal auch nur NEXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine in durch (siehe Landau-Notation) beschränkter Zeit akzeptiert werden können. Hierbei ist ein beliebiges Polynom von der Eingabelänge . In der DTIME-Notation ausgedrückt gilt also:
rdf:langString
En théorie de la complexité, NEXPTIME, ou NEXP, est une classe de complexité, c'est-à-dire un ensemble de problèmes de décision. Plus précisément, c'est l'ensemble des problèmes de décision qui peuvent se résoudre sur une machine de Turing non déterministe en temps O(2p(n)) avec certains polynômes « p »(n), et un espace mémoire illimité. C'est donc la version non-déterministe de EXPTIME.
rdf:langString
計算複雑性理論において、複雑性クラス NEXPTIME（NEXP）とは、非決定性チューリング機械で O(2p(n)) の時間（p(n) は任意の多項式）と無制限の領域を使って解ける決定問題の集合である。 NTIMEの記法では以下のように表される。 重要な NEXPTIME完全な問題として succinct circuit（簡潔回路）がある。succinct circuit は指数関数的に少ない空間でグラフを表すのに使われる単純な機械である。入力ノード数と出力ノード数を入力とし、それらの間にエッジを張る。隣接行列のような普通のグラフ表現で同じ問題を解こうとする場合はNP完全となるが、succinct circuit では入力に要するビット数が指数関数的に少ないため、NEXPTIME完全となる。例えば、succinct circuit を使ってグラフのハミルトン路を探す問題は NEXPTIME完全である。 なお、P=NP であった場合、NEXPTIME=EXPTIME となることに注意されたい。
rdf:langString
在計算複雜度理論內，複雜度類NEXPTIME（有時叫做NEXP）是一個決定性問題的集合，包含可以使用非確定型圖靈機，使用O(2p(n))（這裡的p(n)是某個多項式）的時間可以解決的問題。另外這裡不限制空間的使用。 以NTIME作定義 一個很重要的NEXPTIME-完全問題集合與簡潔電路（succinct circuit）有關。簡潔電路是能以指數速率縮減的空間形容圖的一個機器。這個機器接收兩個頂點的號碼為輸入，輸出這兩個頂點是否有邊相連。如果有個問題，使用一般的圖表示法，像是連接矩陣，去解決時是個NP-完全問題，那麼使用簡潔電路的表示來解決這個問題是NEXPTIME-完全，因為輸入的大小跟前者相比是成指數速率縮小。舉個簡單的例子，使用簡潔電路的表示法找一張圖的哈密頓圖是NEXPTIME-完全。 如果P = NP，那麼NEXPTIME = EXPTIME；更精確的說，E ≠ NE，若且唯若存在一個稀疏語言，在NP並且不在P裡面。
rdf:langString
En teoria de la complexitat, la classe de complexitat NEXPTIME és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai O (2p(n)), on p(n) és una funció polinomial sobre n. En termes de NTIME es té També es pot definir NEXPTIME usant màquines de Turing deterministes com a verificadors. Un llenguatge L és a NEXPTIME si i només si existeixen els polinomis p i q i una màquina de Turing determinista M tal que: Sabem que P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME i també, pel teorema de la jerarquia del temps que NP ⊊ NEXPTIME
rdf:langString
In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time . In terms of NTIME, Alternatively, NEXPTIME can be defined using deterministic Turing machines as verifiers. A language L is in NEXPTIME if and only if there exist polynomials p and q, and a deterministic Turing machine M, such that
* For all x and y, the machine M runs in time on input
* For all x in L, there exists a string y of length such that
* For all x not in L and all strings y of length ,
rdf:langString
Em teoria da complexidade, NEXPSPACE (também chamada de NEXP) é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing não determinística em espaço O(2p(n)) para uma dada p(n) e espaço ilimitado. Em termos de NTIME, temos que Se P = NP, então NEXPTIME = EXPTIME; mais precisamente, E ≠ se e somente se existe uma linguagem em NP que não está em P.
rdf:langString
rdf:langString
NEXPTIME
rdf:langString
NEXPTIME
rdf:langString
NEXPTIME
rdf:langString
NEXPTIME
rdf:langString
NEXPTIME
rdf:langString
NEXPTIME
rdf:langString
NEXPTIME
rdf:langString
NEXPTIME
xsd:integer
663657
xsd:integer
1075441438
rdf:langString
En teoria de la complexitat, la classe de complexitat NEXPTIME és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai O (2p(n)), on p(n) és una funció polinomial sobre n. En termes de NTIME es té També es pot definir NEXPTIME usant màquines de Turing deterministes com a verificadors. Un llenguatge L és a NEXPTIME si i només si existeixen els polinomis p i q i una màquina de Turing determinista M tal que:
* Per tot x i y , la màquina M s'executa en temps per l'entrada
* Per tot x a L, existeix una cadena y de longitud tal que
* Per tot x no a L i totes les cadenes y de longitud , Sabem que P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME i també, pel teorema de la jerarquia del temps que NP ⊊ NEXPTIME Si P = NP, llavors NEXPTIME = EXPTIME, més precisament E ≠ NE si i només si existeixen llenguatges escassos a NP que no estan a P.
rdf:langString
En teoría de la complejidad computacional, la clase de complejidad NEXPTIME es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en tiempo O(2p(n)), donde p(n) es una función polinomial sobre n. En función de NTIME,
* Datos: Q1575791
rdf:langString
In der Komplexitätstheorie steht NEXPTIME (manchmal auch nur NEXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine in durch (siehe Landau-Notation) beschränkter Zeit akzeptiert werden können. Hierbei ist ein beliebiges Polynom von der Eingabelänge . In der DTIME-Notation ausgedrückt gilt also:
rdf:langString
In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time . In terms of NTIME, Alternatively, NEXPTIME can be defined using deterministic Turing machines as verifiers. A language L is in NEXPTIME if and only if there exist polynomials p and q, and a deterministic Turing machine M, such that
* For all x and y, the machine M runs in time on input
* For all x in L, there exists a string y of length such that
* For all x not in L and all strings y of length , We know P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME and also, by the time hierarchy theorem, that NP ⊊ NEXPTIME If P = NP, then NEXPTIME = EXPTIME (padding argument); more precisely, E ≠ NE if and only if there exist sparse languages in NP that are not in P.
rdf:langString
En théorie de la complexité, NEXPTIME, ou NEXP, est une classe de complexité, c'est-à-dire un ensemble de problèmes de décision. Plus précisément, c'est l'ensemble des problèmes de décision qui peuvent se résoudre sur une machine de Turing non déterministe en temps O(2p(n)) avec certains polynômes « p »(n), et un espace mémoire illimité. C'est donc la version non-déterministe de EXPTIME.
rdf:langString
計算複雑性理論において、複雑性クラス NEXPTIME（NEXP）とは、非決定性チューリング機械で O(2p(n)) の時間（p(n) は任意の多項式）と無制限の領域を使って解ける決定問題の集合である。 NTIMEの記法では以下のように表される。 重要な NEXPTIME完全な問題として succinct circuit（簡潔回路）がある。succinct circuit は指数関数的に少ない空間でグラフを表すのに使われる単純な機械である。入力ノード数と出力ノード数を入力とし、それらの間にエッジを張る。隣接行列のような普通のグラフ表現で同じ問題を解こうとする場合はNP完全となるが、succinct circuit では入力に要するビット数が指数関数的に少ないため、NEXPTIME完全となる。例えば、succinct circuit を使ってグラフのハミルトン路を探す問題は NEXPTIME完全である。 なお、P=NP であった場合、NEXPTIME=EXPTIME となることに注意されたい。
rdf:langString
Em teoria da complexidade, NEXPSPACE (também chamada de NEXP) é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing não determinística em espaço O(2p(n)) para uma dada p(n) e espaço ilimitado. Em termos de NTIME, temos que Um importante conjunto de problemas NEXPTIME-completos estão relacionados à circuitos sucintos. Circuitos sucintos são simplesmente máquinas que descrevem grafos em espaço exponencialmente menor. Estes aceitam dois números de vértices como entrada e saída se existe uma ligação entre eles. Se solucionar um problema em um grafo em uma representação natural, tal como matrix de adjacencia, é NP-completo, então solucionar o mesmo problema em uma reapresentação de circuitos sucinto é NEXPTIME-completo, porque a entrada é exponencialmente menor. Ou seja, encontrar um caminho hamiltoniano para um grafo codificado de tal forma é NEXPTIME-completo. Se P = NP, então NEXPTIME = EXPTIME; mais precisamente, E ≠ se e somente se existe uma linguagem em NP que não está em P.
rdf:langString
在計算複雜度理論內，複雜度類NEXPTIME（有時叫做NEXP）是一個決定性問題的集合，包含可以使用非確定型圖靈機，使用O(2p(n))（這裡的p(n)是某個多項式）的時間可以解決的問題。另外這裡不限制空間的使用。 以NTIME作定義 一個很重要的NEXPTIME-完全問題集合與簡潔電路（succinct circuit）有關。簡潔電路是能以指數速率縮減的空間形容圖的一個機器。這個機器接收兩個頂點的號碼為輸入，輸出這兩個頂點是否有邊相連。如果有個問題，使用一般的圖表示法，像是連接矩陣，去解決時是個NP-完全問題，那麼使用簡潔電路的表示來解決這個問題是NEXPTIME-完全，因為輸入的大小跟前者相比是成指數速率縮小。舉個簡單的例子，使用簡潔電路的表示法找一張圖的哈密頓圖是NEXPTIME-完全。 如果P = NP，那麼NEXPTIME = EXPTIME；更精確的說，E ≠ NE，若且唯若存在一個稀疏語言，在NP並且不在P裡面。
xsd:nonNegativeInteger
5964