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

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.

• 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? – Dmitry Dec 5 '20 at 18:52
• 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. – Gabi G Dec 5 '20 at 19:11

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.