so i've come across this category of complexity a couple of times, and finally got around to reading it up (page 155 of Garey & Johnson"Computers and Intractability, if you must:-)
its a slightly refined way of looking at a sub class (but a large sub class) at the "harder" end of NP- - basically, instead of just decidability, a Non Deterministic Counting Turing Machine (TM:-) tells you "how many". (hence the #)
so in problems like maximal matching pairs on a bi-partite graph (e.g. call assignment problem in circuit switched net, or route/scedule problem in multihop radio) which can be "reduced" to a set packing problem (and knowing how many makes it a #P equiv to set packing)
Computational Complexity of Loss Networks
No comments:
Post a Comment