Notices
Results 1 to 1 of 1

Thread: Complexity problem

  1. #1 Complexity problem 
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    I'm trying to place a puzzle in the complexity hierarchy, and I need a bit of help. The puzzle looks like this:

    1: 5, 6, !7
    2: 4, !5
    3: !4, 7
    4: !1, !2, !3
    5: !1, !2, !3
    6: !1, !2, !3
    7: !1, !2, !3
    8: 1, 2, 3

    And the rules are, each number is a switch followed by a set of conditions that must be met to be able to flip that switch. So to flip switch 1 (either on or off), you need to first make sure switches 5 and 6 are on and 7 is off. The goal is to turn the last switch on.

    It's easy to see that this problem is in PSPACE, and the above problem solves the SAT problem for the boolean formula , where 1 2 3 are the clauses and 4 5 6 7 are the variables. The general construction used proves it's NP-hard.

    There's also a construction that shows that this problem can generate solutions of exponential length, which means it's (almost certainly) not in NP, but so far I can't prove it's PSPACE-complete (I can't figure out how to incorporate universal qualifiers with a polynomial number of extra switches).

    Anyway, my question is basically just whether or not anyone recognizes this and whether or not anyone familar with PSPACE can give me any advice.

    Edit: I just realized my SAT construction isn't quite right. I'll fix it as soon as I figure out what I did wrong.

    Hmm... As written, I think my puzzle is somewhat broken, but the simple fix is to allow the conditions to be a set of sets of switches instead and you need to match at least one set to flip the switch. Then you'd rewrite the conditions as:

    1: {5}, {6}, {!7}
    2: {4}, {!5}
    3: {!4}, {7}
    4: {!1, !2, !3}
    5: {!1, !2, !3}
    6: {!1, !2, !3}
    7: {!1, !2, !3}
    8: {1, 2, 3}

    Of course, it'd be nice if that wasn't needed. Anyway, now I have two puzzles to try and place.


    Reply With Quote  
     

  2.  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •