Assume $SAT$ is in $QuasiP$. We immediately infer $NQuasiP=QuasiP$ and $EXP=NEXP$. From https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf we infer $NQuasiP$ is not in $P/poly$ which implies $NQuasiP\neq ZPP$.

Now if $SAT$ reduces $MCSP$ by $LOGSPACE$ $m$-reductions we infer a stronger separation of $PSPACE\neq ZPP$ by https://drops.dagstuhl.de/opus/volltexte/2015/5074/.

  1. I am wondering if $SAT$ is in $TISP(QuasiPTIME, QuasiLOGSPACE)$ will provide $PSPACE\not\subseteq P/poly$ and $PSPACE\neq ZPP$?

I think at least $SAT$ in $TISP(PTIME, LOGSPACE)$ will provide $PSPACE\not\subseteq P/poly$ and $PSPACE\neq ZPP$.

  1. Does faster $SAT$ provide implications to $SAT$ to $MCSP$ reductions or vice versa?

1 Answer 1

  1. If SAT is in polylog space then PH should also be in polylog space, since the typical complete problems work under logspace reductions. By padding this implies e.g. Sigma3EXP is in PSPACE. So yes, in this case PSPACE is not in P/poly but moreover PSPACE has functions requiring maximum circuit complexity. At any rate the algorithmic hypothesis here is a lot more unlikely than the lower bound conclusion, in my mind, so I'm not sure how interesting this implication is.

(Note SAT in QuasiP would imply EXP has functions of maximum circuit complexity, for similar reasons.)

  1. Definitely if SAT has fast enough algorithms then MCSP has faster algorithms due to SAT's NP-completeness. Beyond that I don't see an immediate connection
  • $\begingroup$ EXP (and E) has maximum circuit complexity is not faulty. Both SAT in P or QuasiP and MCSP in P provides these I think. $\endgroup$
    – Turbo
    Feb 12, 2021 at 15:29
  • $\begingroup$ SAT is in quasiP implies $NquasiP=QuasiP$ and $EXP=NEXP$ and doesn't it mean (utilizing time hierarchy) $QuasiP\subsetneq EXP=\Sigma_3EXP$? So is it possible following $$NP=CH\subseteq TISP(PTIME, LOGSPACE)\subsetneq QuasiP=TISP(QuasiPTIME, polylogspace))\subsetneq EXP=\Sigma_3EXP=PSPACE=TISP(EXPTIME, POLYSPACE))$$ is not unequivocally ruled out? $\endgroup$
    – Turbo
    Feb 12, 2021 at 15:58
  • $\begingroup$ I guess $LOGSPACE$ containing $CH$ implies $EXP$ in $PSPACE$ is standard result. $\endgroup$
    – Turbo
    Feb 12, 2021 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.