The User Authorization Query (UAQ) Problem is a key issue related to efficient handling of users’ access requests in Role Based Access Control (RBAC) systems. However, there may not exist any solution to a given UAQ problem due to the limitation caused by the current system state, because missing any requested permission may thwart a task, while an extra permission may bring an intolerable risk to the system. Hence, update of the role–permission assignment is needed to support the feasibility of an UAQ problem. In this paper, we study fundamental problems related to role–permission reassignment, including the RVP problem the goal of which is to determine whether a given role–permission assignment satisfies all reassignment objectives and does not violate any prerequisite constraint or permission-capacity constraint, the RFP problem which verifies whether there exists a valid role–permission assignment, and the RGP problem which studies how to generate a valid role–permission assignment. We present the computational complexity analysis of RVP, RFP and RGP, showing that RVP is solvable in linear time, while both RFP and RGP are NP-hard. We also propose an approach for RGP, which incorporates a preprocessing to decrease the size of the problem, and reduce it to an SAT problem. Finally, experimental results show the validity and effectiveness of our proposed approach.