In computational complexity theory, the complexity class NE is the set of decision problems that can be solved by a non-deterministic Turing machine in time O(kn) for some k. NE, unlike the similar class NEXPTIME, is not closed under polynomial-time many-one reductions.
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| - NE (Complexitat) (ca)
- NE (complexité) (fr)
- NE (complexity) (en)
- NE (複雜度) (zh)
|
rdfs:comment
| - En teoria de la complexitat, la classe de complexitat NE és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en temps O(kn) per algun k. (ca)
- En informatique théorique et notamment en théorie de la complexité, la classe NE est une classe de complexité ; c'est l'ensemble des problèmes de décision qui peuvent être décidés par une machine de Turing non déterministe en temps exponentiel avec un exposant linéaire. C'est une classe de complexité d'importance mineure. (fr)
- In computational complexity theory, the complexity class NE is the set of decision problems that can be solved by a non-deterministic Turing machine in time O(kn) for some k. NE, unlike the similar class NEXPTIME, is not closed under polynomial-time many-one reductions. (en)
- 在計算複雜度理論內,複雜度類 NE是一個決定型問題的集合,包含能使用非決定型圖靈機,在O(kn) (k是某個常數)時間內解決的問題。 NE與相近的類別NEXPTIME不同,在多項式時間多對一歸約時並不封閉。 (zh)
|
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 NE és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en temps O(kn) per algun k. (ca)
- En informatique théorique et notamment en théorie de la complexité, la classe NE est une classe de complexité ; c'est l'ensemble des problèmes de décision qui peuvent être décidés par une machine de Turing non déterministe en temps exponentiel avec un exposant linéaire. C'est une classe de complexité d'importance mineure. (fr)
- In computational complexity theory, the complexity class NE is the set of decision problems that can be solved by a non-deterministic Turing machine in time O(kn) for some k. NE, unlike the similar class NEXPTIME, is not closed under polynomial-time many-one reductions. (en)
- 在計算複雜度理論內,複雜度類 NE是一個決定型問題的集合,包含能使用非決定型圖靈機,在O(kn) (k是某個常數)時間內解決的問題。 NE與相近的類別NEXPTIME不同,在多項式時間多對一歸約時並不封閉。 (zh)
|
gold:hypernym
| |
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage disambiguates
of | |
is foaf:primaryTopic
of | |