Skip to main content
MathOverflow

Return to Answer

added 4 characters in body
Source Link
user6976
user6976

There is also the famous algebraic characterization of NP by Fagin (Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation. SIAM-AMS Proceedings. 7, 43--73, 1974):

The membership problem for an abstract (i.e. closed under isomorphisms) class of finite algebraic systems is in NP if and only if it is the class of all finite models of a second-order formula of the following type: $$\exists Q_1\exists Q_2\ldots \exists Q_n (\Theta)$$ where $Q_i$ is a predicate, and $\Theta$ is a first-order formula.

This also gives an algebraic characterization of P=NP. 

Also the Constraint Satisfaction Problem gives another algebraic approach to P=NP. That problem is very popular in Universal Algebra now (see, for example, Barto, Libor, Kozik, Marcin, Constraint satisfaction problems of bounded width. 2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), 595–603, IEEE Computer Soc., Los Alamitos, CA, 2009.)

There is also the famous algebraic characterization of NP by Fagin (Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation. SIAM-AMS Proceedings. 7, 43--73, 1974):

The membership problem for an abstract (i.e. closed under isomorphisms) class of finite algebraic systems is in NP if and only if it is the class of all finite models of a second-order formula of the following type: $$\exists Q_1\exists Q_2\ldots \exists Q_n (\Theta)$$ where $Q_i$ is a predicate, and $\Theta$ is a first-order formula.

This also gives an algebraic characterization of P=NP. Also the Constraint Satisfaction Problem gives another algebraic approach to P=NP. That problem is very popular in Universal Algebra now (see, for example, Barto, Libor, Kozik, Marcin, Constraint satisfaction problems of bounded width. 2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), 595–603, IEEE Computer Soc., Los Alamitos, CA, 2009.)

There is also the famous algebraic characterization of NP by Fagin (Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation. SIAM-AMS Proceedings. 7, 43--73, 1974):

The membership problem for an abstract (i.e. closed under isomorphisms) class of finite algebraic systems is in NP if and only if it is the class of all finite models of a second-order formula of the following type: $$\exists Q_1\exists Q_2\ldots \exists Q_n (\Theta)$$ where $Q_i$ is a predicate, and $\Theta$ is a first-order formula.

This also gives an algebraic characterization of P=NP. 

Also the Constraint Satisfaction Problem gives another algebraic approach to P=NP. That problem is very popular in Universal Algebra now (see, for example, Barto, Libor, Kozik, Marcin, Constraint satisfaction problems of bounded width. 2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), 595–603, IEEE Computer Soc., Los Alamitos, CA, 2009.)

Source Link
user6976
user6976

There is also the famous algebraic characterization of NP by Fagin (Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation. SIAM-AMS Proceedings. 7, 43--73, 1974):

The membership problem for an abstract (i.e. closed under isomorphisms) class of finite algebraic systems is in NP if and only if it is the class of all finite models of a second-order formula of the following type: $$\exists Q_1\exists Q_2\ldots \exists Q_n (\Theta)$$ where $Q_i$ is a predicate, and $\Theta$ is a first-order formula.

This also gives an algebraic characterization of P=NP. Also the Constraint Satisfaction Problem gives another algebraic approach to P=NP. That problem is very popular in Universal Algebra now (see, for example, Barto, Libor, Kozik, Marcin, Constraint satisfaction problems of bounded width. 2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), 595–603, IEEE Computer Soc., Los Alamitos, CA, 2009.)