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.
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| - S2P (Complexitat) (ca)
- S2P (complexity) (en)
|
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)
|
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
Link from a Wikipage to an external page
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
b
| |
p
| |
has 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)
|
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is foaf:primaryTopic
of | |