No-signaling, intractability and entanglement