In 1974, Fagin showed that it is equivalent to languages representing structures definable by sigma-1-1 sentences, and Blum showed that the circuit size of a member of it is lower bounded by 3n. Razoborov showed that a a problem in its deterministic counterpart, PERFECT-MATCHING, and a problem in it, CLIQUE, both require exponential monotone circui
In 1974, Fagin showed that it is equivalent to languages representing structures definable by sigma-1-1 sentences, and Blum showed that the circuit size of a member of it is lower bounded by 3n. Razoborov showed that a a problem in its deterministic counterpart, PERFECT-MATCHING, and a problem in it, CLIQUE, both require exponential monotone circuits. In 1972, Edmond Karp showed that many problems like KNAPSACK and CHROMATIC NUMBER are complete for it, extending Cook and Levin's demonstration of SATISFIABILITY's completeness for it. For 10 points, name this complexity class of problems solvable in nondeterministic polynomial time that may or may not be equal to P.
In 1974, Fagin showed that it is equivalent to languages representing structures definable by sigma-1-1 sentences, and Blum showed that the circuit size of a member of it is lower bounded by 3n.
{N}ondeterministic {P}olynomial