S2P (complexity)
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.
Link from a Wikipage to another Wikipage
primaryTopic
S2P (complexity)
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.
has abstract
En teoria de la complexitat, l ...... , on y i z son polinomis de x.
@ca
In computational complexity th ...... and z must be polynomial of x.
@en
Link from a Wikipage to an external page
Wikipage page ID
33,541,732
page length (characters) of wiki page
Wikipage revision ID
985,175,223
Link from a Wikipage to another Wikipage
p
P
@en
wikiPageUsesTemplate
subject
comment
En teoria de la complexitat, l ...... , on y i z son polinomis de x.
@ca
In computational complexity th ...... and z must be polynomial of x.
@en
label
S2P (Complexitat)
@ca
S2P (complexity)
@en