1
vote
Accepted
Can one find any solution to this matrix problem in polynomial time?
It seems the following very simple algorithm works as long as $\sum_x \text{row}[x]= \sum_y \text{col}[y]$:
...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
np × 121cc.complexity-theory × 73
np-hardness × 23
complexity-classes × 18
np-complete × 17
ds.algorithms × 10
p-vs-np × 7
reference-request × 6
graph-theory × 6
sat × 6
reductions × 6
graph-algorithms × 4
co.combinatorics × 4
conditional-results × 4
approximation-algorithms × 3
quantum-computing × 3
computability × 3
time-complexity × 3
cr.crypto-security × 3
lower-bounds × 3
turing-machines × 3
open-problem × 3
complexity × 3
proof-complexity × 3
polynomial-hierarchy × 3