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])
The 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.
