UP (complexity) (original) (raw)
في علم التعقيد الحسابي القسم UP هو قسم كل المسائل التي يمكن تقريرها بوقت كثير الحدود على آلة تيورنج ليست حتمية بحيث أنَّه يوجد على الأكثر مسار حساب واحد اجابته «نعم». هذا القسم يحوي P ويحتويه القسم NP .
| Property | Value | |||
|---|---|---|---|---|
| dbo:abstract | في علم التعقيد الحسابي القسم UP هو قسم كل المسائل التي يمكن تقريرها بوقت كثير الحدود على آلة تيورنج ليست حتمية بحيث أنَّه يوجد على الأكثر مسار حساب واحد اجابته «نعم». هذا القسم يحوي P ويحتويه القسم NP . (ar) En teoria de complexitat, la classe de complexitat UP és la classe de problemes de decisió que es poden resoldre en temps polinòmic en una per almenys un camí que accepte per cada entrada. Una reformulació de la definició de la classe NP s'expressa dient que un llenguatge és a NP si i només si donada una resposta, es pot verificar en un temps polinòmic per una màquina de Turing determinista. De manera similar, un llenguatge és a UP si donada una resposta es pot verificar en un temps polinòmic, i el verificador només accepta com a molt una resposta per cada instància del problema. Més formalment, un llenguatge L pertany a UP si existeix un algorisme de dues entrades i temps polinòmic A i una constant c tal que: * si x és de L, llavors existeix un únic certificat y amb tal que * si x no és de L, llavors no existeix un certificat y amb tal que * l'algorisme A verifica L en un temps polinòmic (ca) En teoría de la complejidad computacional, la clase de complejidad UP (tiempo polinómico, no determinista, no ambiguo) es el conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista tal que la solución si existe es única. La clase UP está contenida en NP y contiene a P. No se sabe si estas inclusiones son estrictas. Un lenguaje L pertenece a UP si existe un algoritmo A de tiempo polinómico con dos entradas y una constante c tal que: L = {x in {0,1}* | ∃! valor, y con | y | = O( | x |
| dbo:wikiPageID | 312240 (xsd:integer) | |||
| dbo:wikiPageLength | 2164 (xsd:nonNegativeInteger) | |||
| dbo:wikiPageRevisionID | 951083651 (xsd:integer) | |||
| dbo:wikiPageWikiLink | dbr:NP_(complexity) dbr:Parity_game dbr:Decision_problem dbr:Integer_factorization dbr:Valiant–Vazirani_theorem dbr:Complement_(complexity) dbr:Complete_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:P_(complexity) dbr:Promise_problem dbc:Complexity_classes dbr:Polynomial_time dbr:Unambiguous_Turing_machine | |||
| dbp:wikiPageUsesTemplate | dbt:Refimprove dbt:Reflist dbt:Tmath dbt:ComplexityClasses | |||
| dcterms:subject | dbc:Complexity_classes | |||
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 | |||
| rdfs:comment | في علم التعقيد الحسابي القسم UP هو قسم كل المسائل التي يمكن تقريرها بوقت كثير الحدود على آلة تيورنج ليست حتمية بحيث أنَّه يوجد على الأكثر مسار حساب واحد اجابته «نعم». هذا القسم يحوي P ويحتويه القسم NP . (ar) En teoría de la complejidad computacional, la clase de complejidad UP (tiempo polinómico, no determinista, no ambiguo) es el conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista tal que la solución si existe es única. La clase UP está contenida en NP y contiene a P. No se sabe si estas inclusiones son estrictas. Un lenguaje L pertenece a UP si existe un algoritmo A de tiempo polinómico con dos entradas y una constante c tal que: L = {x in {0,1}* | ∃! valor, y con | y | = O( | x |
| rdfs:label | يو بي (تعقيد حسابي) (ar) UP (Complexitat) (ca) UP (clase de complejidad) (es) UP (complexité) (fr) UP (計算複雑性理論) (ja) UP (복잡도) (ko) UP (complexidade) (pt) UP (complexity) (en) UP (複雜度) (zh) | |||
| owl:sameAs | freebase:UP (complexity) yago-res:UP (complexity) wikidata:UP (complexity) dbpedia-ar:UP (complexity) dbpedia-ca:UP (complexity) dbpedia-es:UP (complexity) dbpedia-fr:UP (complexity) dbpedia-ja:UP (complexity) dbpedia-ko:UP (complexity) dbpedia-pt:UP (complexity) dbpedia-zh:UP (complexity) https://global.dbpedia.org/id/53m79 | |||
| prov:wasDerivedFrom | wikipedia-en:UP_(complexity)?oldid=951083651&ns=0 | |||
| foaf:isPrimaryTopicOf | wikipedia-en:UP_(complexity) | |||
| is dbo:wikiPageDisambiguates of | dbr:Up | |||
| is dbo:wikiPageWikiLink of | dbr:List_of_complexity_classes dbr:Parity_P dbr:Parity_game dbr:Book_embedding dbr:Integer_factorization dbr:Computing_the_permanent dbr:Valiant–Vazirani_theorem dbr:Alan_Selman dbr:Up dbr:Unambiguous_Turing_machine | |||
| is foaf:primaryTopic of | wikipedia-en:UP_(complexity) |