[FOM] some questions about computability theory
phyao1985 at gmail.com
Mon Feb 5 21:48:00 EST 2007
1. Let (C, <T) be the partial order of computably Turing degrees
under Turing reducibilty, and (EXP, <p) be the partial order of EXP
under polynomial reducibility, my question is that whether both of
them are isomorphic or one can imbedded into the other. What about the
case if we replace the EXP by other complexity classes ?
2. Can (C, <T) be axiomable?
More information about the FOM