CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Dec 2009
    Posts
    2

    Question 3-SAT variation, Any Ideas?

    So I have to take a basic 3-SAT problem and solve it in nlog(n) time, OR just n.
    The variation is that you have an array of boolean values, lets call it B
    If clause C contains Bi or ~Bi, and contains Bj or ~Bj, then abs|j-i| <= 10.

    Sooo any Clause can only have boolean values that are MAX 10 index spaces away from eachother in the boolean array.

    I been racking my brain trying to come up with something but... nothing.
    My algorithm must decide if an assignement is possible and if it is, must find that assignment.

    Any ideas? Thank You

  2. #2
    Join Date
    Dec 2009
    Posts
    2

    Re: 3-SAT variation, Any Ideas?

    Forgot to mention n is the number of clauses

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