Help me recognize classical problem in task
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

#### Hybrid View

1. Junior Member
Join Date
Oct 2012
Posts
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)+(z-y)={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)+(x-y) - 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.

2. Elite Member
Join Date
May 2009
Posts
2,413

## Re: Help me recognize classical problem in task

Originally Posted by icegood
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
•