Jump to content

Talk:SO (complexity)

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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)[reply]

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)[reply]

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)[reply]

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.