On symmetric differences of NP-hard sets with weakly P-selective sets (Q1314375)

The possibility and consequences are studied of having an NP-hard set that forms a symmetric difference with an ``easy'' set (like a weakly \(p\)-selective set) that is of ``low information content''. Especially, it is shown that the existence of an NP-hard set \(A\) (with respect to many- one reducibility) that forms a symmetric difference to a weakly \(p\)- selective set \(B\), such that both \(A-B\) and \(B-A\) are bounded-truth-table reducible to a sparse set implies \(\text{P}=\text{NP}\). The proof is based on the tree pruning techniques by Mahaney and Fortune.