CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    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. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Help me recognize classical problem in task

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





Click Here to Expand Forum to Full Width

Featured