Show that if $SAT \in P/klog(n)$ then $SAT \in P$

Assuming that there is a a constant $k \in \mathbb{N}$ such that $SAT \in P/klog(n)$, I need to prove that $SAT \in P$.

Since $SAT \in P/klog(n)$, then there is a sequence of advices $\{a_n\}_{n \in \mathbb{N}}$ of length $|a_n \le klog(n)$ and a turing machine $M$ that runs for at most $n^c$ steps (for some $c \in \mathbb{N}$ such that:

$$\phi \in SAT \Leftrightarrow M(\phi, a_{|\phi|}) = 1 $$

I tried to show a Turing machine $U$ that runs in a polynomial time and solves $SAT$.

$U$ on an input $\phi$:

  1. calculate the size $|\phi|$
  2. write $a_{|\phi|}$ on start of the working tape
  3. simulate $ M(\phi, a_{|\phi|})$ in a way that when $M$ tries to read $a_{|\phi|}$, it will read it from the start of the working tape, and the working tape of $M$ will start from offset $|a_{|\phi|}|$.
  4. $U$ will return the same answer as $M$

Is my answer correct? It seems like I'm missing something

Help would be appreciated.

  • 1
    $\begingroup$ Your approach assumes that for any $|\phi|$ you know $\alpha_{|\phi|}$. You can't encodeall possible advices (for all input lengths) in your algorithm. Hint: how many different advices of length $k \log n$ exist? $\endgroup$ – Dmitry Dec 5 '20 at 18:52
  • $\begingroup$ Okay, I understand. Since there are $n^k$ advices of length $klogn$ then I can check for every one of them, and it will still be polynomial. $\endgroup$ – Gabi G Dec 5 '20 at 19:11

You need to combine two ideas here:

  1. There are only polynomially many possible advice strings.
  2. If you can solve the decision version of SAT, then you can solve the search version of SAT.

There is a slight annoyance that you need the search-to-decision reduction to involve only constantly many different input lengths. Assuming for simplicity that you can perform everything using a single input length $n$, here is what you do: you go over all possible advices for length $n$, and for each one, either determine that the SAT instance is unsatisfiable, or attempt to find a satisfying assignment. If you find a satisfying assignment, then the SAT instance is satisfiable, otherwise it isn't.

I'll let you fill in the details.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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