On the Complexity of Implementing Certain Classes of Shared Objects