Hacker News new | past | comments | ask | show | jobs | submit login

NEXP is nondeterministic exponential time, right? In that case we know that P /= EXPTIME by the time hierarchy theorem and EXPTIME is contained in NEXP. We also have a direct result that NP /= NEXP (reference given in https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nexp).



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: