New answers tagged

0 votes

How can we show that P is not closed under taking all long prefixes?

In fact Yuval's hint is all the solution you need: consider instance $I$ of any $\mathsf{NP}$-complete problem (e.g. 3SAT) and its proof $c$, let the proof appear in the second half of the constructed ...
user avatar
0 votes

How can we show that P is not closed under taking all long prefixes?

Big hint based on Yuvals Hint: Consider the language $\{\langle S, f \rangle | S \text{ is a SAT formula and } f\text{ a satisfying assingment}\} \in P$
user avatar
  • 1,188

Top 50 recent answers are included