Talk:SO (complexity)
Add topic | This redirect does not require a rating on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||
| |||||||||||||||||||||||||
Untitled
[edit]Since they were "First Order" I added "second order" but i don't know if it's good or not. Every remarks I had to do are in the Discussion page of FO Arthur MILCHIOR (talk) 08:09, 8 June 2010 (UTC)
Add reference for claim that Every SO formula is Equivalent to Prenex Form.
[edit]I do not recall the source of this statement in literature. It would be good to add a reference for it. (FWIW, I believe the statement to be correct).
2602:306:3489:9890:38D2:4B14:421D:8C6C (talk) 20:19, 26 February 2015 (UTC)
Almost impenetrable, even for someone versed in FO complexity
[edit]This article is in serious need of attention. Ross Fraser (talk) 00:11, 16 October 2015 (UTC)
Can we rename it and/or merge with Second-Order Logic
[edit]I believe it would be good to rename it because SO is too cryptic. "Complexity of Second-Order Logic" and redirect from SO_(complexity) would be an example of an appropriate entry.
Also, so that people are not misled that this solves P vs NP question, the precise statement of the satisfiability and the role of the ordering relation should be clarified.