This can be formulated and solved as a Mixed Integer Linear Programming (MILP) feasibility problem. Such NP-hard problems are routinely solved in practice, even to fairly large scale, despite being "intractable". For $P$ being $n$ by $n$ with $n$ in the hundreds, it should be easy to solve, and possible with n into the thousands.

The problem is to find a $P$ such that all entries of $P$ are $0$ or $1$, all rows of $P$ sum to $1$,all columns of $P$ sum to $1$, and $APx = 0$.

Formulation in CVX under MATLAB

    cvx_begin
    variable P(n,n) binary
    sum(P,1) == 0
    sum(P,2) == 0
    A*P*x == 0
    cvx_end

Formulation in YALMIP under MATLAB

    P = binvar(n,n,'full')
    optimize([sum(P,1) == 0,sum(P,2) == 0,A*P*x == 0])

Specific solver to use may be optionally specified for either CVX or YALMIP.

I don't claim this is the fastest way to solve the problem, but it is a valid formulation, and if it meets your needs, then it has accomplished something useful, protestations of NP-completeness not withstanding.