<ol>
<li>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.</li>
</ol>
<p>(Note SAT in QuasiP would imply EXP has functions of maximum circuit complexity, for similar reasons.)</p>
<ol start="2">
<li>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</li>
</ol>

CC BY-SA 4.0
2021-02-12T15:29:15.060Z
EXP (and E) has maximum circuit complexity is not faulty. Both SAT in P or QuasiP and MCSP in P provides these I think.
Turbo
CC BY-SA 4.0
2021-02-12T15:58:19.263Z
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?
Turbo
CC BY-SA 4.0
2021-02-12T16:29:46.990Z
I guess $LOGSPACE$ containing $CH$ implies $EXP$ in $PSPACE$ is standard result.
Turbo
CC BY-SA 4.0
2021-02-12T14:27:32.330Z
2021-02-12T14:27:32.330Z
Ryan Williams
<p>Assume <span class="math-container">$SAT$</span> is in <span class="math-container">$QuasiP$</span>. We immediately infer <span class="math-container">$NQuasiP=QuasiP$</span> and <span class="math-container">$EXP=NEXP$</span>. From <a href="https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf" rel="nofollow noreferrer">https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf</a> we infer <span class="math-container">$NQuasiP$</span> is not in <span class="math-container">$P/poly$</span> which implies <span class="math-container">$NQuasiP\neq ZPP$</span>.</p>
<p>Now if <span class="math-container">$SAT$</span> reduces <span class="math-container">$MCSP$</span> by <span class="math-container">$LOGSPACE$</span> <span class="math-container">$m$</span>-reductions we infer a stronger separation of <span class="math-container">$PSPACE\neq ZPP$</span> by <a href="https://drops.dagstuhl.de/opus/volltexte/2015/5074/" rel="nofollow noreferrer">https://drops.dagstuhl.de/opus/volltexte/2015/5074/</a>.</p>
<ol>
<li>I am wondering if <span class="math-container">$SAT$</span> is in <span class="math-container">$TISP(QuasiPTIME, QuasiLOGSPACE)$</span> will provide <span class="math-container">$PSPACE\not\subseteq P/poly$</span> and <span class="math-container">$PSPACE\neq ZPP$</span>?</li>
</ol>
<p>I think at least <span class="math-container">$SAT$</span> in <span class="math-container">$TISP(PTIME, LOGSPACE)$</span> will provide <span class="math-container">$PSPACE\not\subseteq P/poly$</span> and <span class="math-container">$PSPACE\neq ZPP$</span>.</p>
<ol start="2">
<li>Does faster <span class="math-container">$SAT$</span> provide implications to <span class="math-container">$SAT$</span> to <span class="math-container">$MCSP$</span> reductions or vice versa?</li>
</ol>

<cc.complexity-theory><complexity-classes><sat><lower-bounds><logspace>
Comparing SAT to MCSP reduction class separations and faster SAT class separations?
Turbo
# Comparing SAT to MCSP reduction class separations and faster SAT class separations?

(Asked by: username_0 on 2021-02-11)

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$.

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

**Tags:** cc.complexity-theory, complexity-classes, sat, lower-bounds, logspace


---

## 1 answers

### Answer by username_1 on 2021-02-12. Score: 2 | Accepted answer

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.)

2. 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

> **Comments:**
> **username_0**: EXP (and E) has maximum circuit complexity is not faulty. Both SAT in P or QuasiP and MCSP in P provides these I think.  
> **username_0**: 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?  
> **username_0**: I guess $LOGSPACE$ containing $CH$ implies $EXP$ in $PSPACE$ is standard result.  

---

