<p>Yes. All advice strings of length log n can be cycled though in polynomial time.
The polynomial time algorithm for SAT would be:
For each of the polynomially many advice strings, try to use it to produce a satisfying assignment for SAT (using self-reducibility) in polynomial time. I would guess this is in the original Karp Lipton paper.</p>

CC BY-SA 3.0
2014-03-14T21:46:32.553Z
Please don't answer clearly off-topic questions.
Kaveh
CC BY-SA 3.0
2014-03-15T22:02:55.843Z
if its in a paper somewhere, seems acceptable/useful at least as `reference-request` :)
vzn
CC BY-SA 3.0
2014-03-16T04:56:43.910Z
it's a corollary of a result that's in a textbook.
Suresh Venkat
CC BY-SA 3.0
2014-03-14T21:27:52.730Z
2014-03-14T21:27:52.730Z
d. patrick
<p>I am trying to either prove or refute the claim mentioned in the title.
Any ideas ?</p>

CC BY-SA 3.0
2014-03-14T21:41:55.283Z
Please read [about] and [help/on-topic]. Questions at the level of typical textbook exercises are off-topic here.
Kaveh
<cc.complexity-theory><p-vs-np><advice-and-nonuniformity>
Assume that $\mathsf{NP} \subseteq \mathsf{P}/\text{log(n)}$, does it imply that $\mathsf{P} = \mathsf{NP}$?
Robert777
# Assume that $\mathsf{NP} \subseteq \mathsf{P}/\text{log(n)}$, does it imply that $\mathsf{P} = \mathsf{NP}$?

(Asked by: username_0 on 2014-03-14)

I am trying to either prove or refute the claim mentioned in the title.
Any ideas ?

**Tags:** cc.complexity-theory, p-vs-np, advice-and-nonuniformity
> **Comments:**
> **username_1**: Please read [about] and [help/on-topic]. Questions at the level of typical textbook exercises are off-topic here.  

---

## 1 answers

### Answer by username_2 on 2014-03-14. Score: 3 | Accepted answer

Yes. All advice strings of length log n can be cycled though in polynomial time.
The polynomial time algorithm for SAT would be:
For each of the polynomially many advice strings, try to use it to produce a satisfying assignment for SAT (using self-reducibility) in polynomial time. I would guess this is in the original Karp Lipton paper.

> **Comments:**
> **username_1**: Please don't answer clearly off-topic questions.  
> **username_3**: if its in a paper somewhere, seems acceptable/useful at least as `reference-request` :)  
> **username_4**: it's a corollary of a result that's in a textbook.  

---

