| dbo:abstract
|
- En teoria de la complexitat, la classe de complexitat SP2 és la classe de complexitat intermèdia entre el primer i segon nivell de la jerarquia polinòmica. Un llenguatge L és a SP2 si existeix un predicat P de temps polinòmic tal que:
* si , llavors existeix un y tal que per tot z,
* si , llavors existeix un z tal que per tot y, on y i z son polinomis de x. (ca)
- In computational complexity theory, SP2 is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language L is in if there exists a polynomial-time predicate P such that
* If , then there exists a y such that for all z, ,
* If , then there exists a z such that for all y, , where size of y and z must be polynomial of x. (en)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4166 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:b
| |
| dbp:p
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En teoria de la complexitat, la classe de complexitat SP2 és la classe de complexitat intermèdia entre el primer i segon nivell de la jerarquia polinòmica. Un llenguatge L és a SP2 si existeix un predicat P de temps polinòmic tal que:
* si , llavors existeix un y tal que per tot z,
* si , llavors existeix un z tal que per tot y, on y i z son polinomis de x. (ca)
- In computational complexity theory, SP2 is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language L is in if there exists a polynomial-time predicate P such that
* If , then there exists a y such that for all z, ,
* If , then there exists a z such that for all y, , where size of y and z must be polynomial of x. (en)
|
| rdfs:label
|
- S2P (Complexitat) (ca)
- S2P (complexity) (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
