We know $ETH$ is a reasonable barrier to solving $SAT$ efficiently. We have $SAT$ reducing randomly to promise unique $SAT$ by $VV$. However we do not know if $VV$ can be derandomized. Given the situation is there anything that we know as of the knowledge we have that $ETH$ remains a barrier to solving promise unique $SAT$ problems efficiently?
$\begingroup$
$\endgroup$
Add a comment
|