New answers tagged np
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 ...
- 98
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$
- 1,188
Top 50 recent answers are included