
October 5th, 2012, 03:16 PM
#1
Help me recognize classical problem in task
There is a task. For given lattice (isotropic discrete abelian group ) in R^3 for every vertice y let M(y)  set of neighbour vertices (not necessarily closest one's, for other vertice z: M(z)=M(y)+(zy)={a+z=y a \in M(y)}).
Find a mininmal with respect to cardinal subset B(y) of M(y) such that for every x \in M(y) :
B(y) \intersection B(x) isn't empty. (B(x)=B(y)+(xy)  again isotropical translation).
It seems to be NP problem but in which cases it could be solved
or at least equivalent tasks couldn't be obtained.

October 6th, 2012, 02:18 PM
#2
Re: Help me recognize classical problem in task
Originally Posted by icegood
There is a task.
I don't understand your formalism. Please explain the problem in layman terms without the abstract lingo. Preferably with an example. And where's the algorithm?
Also, the fact that a problem is NP complete doesn't mean it cannot be solved. It can, only not in polynominal time.
Last edited by nuzzle; October 7th, 2012 at 04:25 AM.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
