[FOM] Questions in descriptive complexity

Walid Gomaa walid.gomaa at gmail.com
Thu Feb 21 08:19:52 EST 2008


(1) is it still open that graph connectivity is not expressible in
$mon\Sigma_11$ even in the presence of arbitrary built-in relations?
(2) is there some $NP$ problem proven not to be expressible in $bin\Sigma_11$?


More information about the FOM mailing list