S2P (complexity)
id:
s2p-complexity-296-13176095
title:
S2P (complexity)
text:
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 S 2 P if there exists a polynomial-time predicate P such that If x ∈ L , then there exists a y such that for all z, P = 1 ,
If x ∉ L , then there exists a z such that for all y, P = 0 , where size of y and z must be polynomial of x.
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/S2P_(complexity)
date created:
date modified:
2021-07-05T16:28:32Z
main entity:
{"identifier":"Q7388242","url":"https://www.wikidata.org/entity/Q7388242"}
image:
fields total:
13
integrity:
13