only existential second-order quantification (over relations) is allowed and only universal first-order quantification (over vertices) is allowed.If existential quantification over vertices were also allowed, the resulting complexity class would be equal to NP (more precisely, the class of those properties of relational structures that are in NP), a fact known as Fagin's theorem.

For example, SNP contains 3-Coloring (the problem of determining whether a given graph is 3-colorable),