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 ...
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$
Top 50 recent answers are included
Related Tags
np × 670complexity-theory × 402
np-complete × 281
np-hard × 148
reductions × 91
decision-problem × 74
graphs × 54
time-complexity × 51
complexity-classes × 50
algorithms × 48
p-vs-np × 46
turing-machines × 43
satisfiability × 40
co-np × 36
polynomial-time × 30
computability × 27
optimization × 21
nondeterminism × 21
polynomial-time-reductions × 17
closure-properties × 15
proof-techniques × 13
3-sat × 12
traveling-salesman × 9
approximation × 8
algorithm-analysis × 7