[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 mailing list