6
$\begingroup$

The description of this game is already exists in this link

I am quoting from this link the description of the game to ease the reading of this question:

In a game, where there are m active bombs, each one with a number above zero, and n standing levers, where each can be either pushed forward or pulled backward, and each lever is connected to some bombs with green wires/cables and connected to some bombs with red wires/cables.

If any lever is pushed forward then all bombs that are connected to this lever via green wire/cable are defused and all bombs that are connected to this lever via red wire/cable, their number is decremented by 1.

If any lever is pulled backward then all bombs that are connected to this lever via red wire/cable are defused and all bombs that are connected to this lever via green wire/cable, their number is decremented by 1.

A defused bomb cannot explode, but any active bomb that it's number reaches zero explodes immediately.

Only standing levers can be touched (either pushed forward or pulled backward). You shouldn't touch already touched (either pushed forward or pulled backward) levers.

To win/beat the game the purpose is to defuse all the active bombs without exploding any of them.

My greedy algorithm described in this question suppose to run in polynomial time, but it's not proven if it is correct.

Even though proving it's correctness is very difficult for me I am attempting to prove it, but this question isn't about this greedy algorithm at all.

Now this question is more general:

Can deterministic Turing machine beats/wins the game described in this question in polynomial time?

If yes, then there should exist polynomial time algorithm that returns all steps that should be followed to beat/win the given instance of this game (if it is possible).

The deterministic Turing machine or the algorithm doesn't have to be greedy necessarily.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I invented this problem myself. $\endgroup$ – Farewell Stack Exchange Jul 19 '17 at 9:22
  • $\begingroup$ The goal of the game is to defuse all the bombs without letting any bomb to explode. I have already said in the description how to defuse bombs and how to explode a bomb. $\endgroup$ – Farewell Stack Exchange Jul 19 '17 at 10:11
  • $\begingroup$ Can we observe the numbers on the bombs? Are we told which levers are connected to which bombs? $\endgroup$ – D.W.♦ Jul 19 '17 at 15:26
  • $\begingroup$ Your question is rhetorical, I mean of course you can observe the numbers on the bombs, they are displayed on the screen of each bomb and obviously that you can see all wires, the color of each (either green or red) and so you know which bombs each lever is connected to. Sorry that I didn't provide this information in the question before, because I didn't think this is necessary. I thought these questions are rhetorical and obvious. If you can't know the number of each bomb and the connection of each lever with each bomb, you will have to guess the correct actions to win the game (if possible) $\endgroup$ – Farewell Stack Exchange Jul 19 '17 at 18:33
5
+100
$\begingroup$

Your problem is NP-hard. It is an easy proof In fact, it is NP-complete because we can reduce it to SAT in polynomial time

We reduce 3-SAT to your problem.

We have a lever for each variable and a bomb for each clause, the red cables are connected to clauses/bombs that have positive literals belonging to that variable/lever and the green cables are connected to clauses/bombs that have negative literals belonging to that variable/lever.

Each bomb has the number 3 written on it, meaning that the bomb will explode if it is decremented three times. Whenever we set a lever that is connected to the bomb in the direction that doesn´t deffuse the bomb we decrement the counter in the bomb. This is the same as setting a variable true if the literal in a clause is false or viceversa. If we do this three times that means that the clause has not being satisfied in the original 3-SAT problem and the bomb explodes.

If the instance is satisfiable, you can always choose the right positions for the levers so that no bomb explodes. If there is a variable assignment that satisfies the clauses that means that the bombs can be defused. A defused bomb cannot explode anymore so that we don´t have to worry about a defused bomb anymore.

So, can your problem be solved in polynomial time? We don´t know. People will have to give a solution to the P vs NP problem first, come back in a hundred years and maybe we will have an answer

|cite|improve this answer
$\endgroup$
  • $\begingroup$ You were right on everything you said. If the CNF instance is satisfiable, then it is possible to defuse all bombs without exploding any of them. But if the CNF instance is unsatisfiable, then this is impossible to defuse all bombs without exploding any of them. $\endgroup$ – Farewell Stack Exchange Jul 28 '17 at 6:16
  • 3
    $\begingroup$ @D.W. I don't think order matters because each bomb has at most 3 levers and is labelled 3. A bomb can only explode if all of its levers are set so any setting of levers that defuses all bombs can be done in any order without risk of explosion. $\endgroup$ – Tomoki Jul 28 '17 at 16:47
  • 1
    $\begingroup$ @Tomoki, ahh, yes, excellent point! I guess we're assuming that every lever must be either pushed forward or pulled backwards (you can't leave any lever in its original position). Makes sense. Thank you for explaining! $\endgroup$ – D.W.♦ Jul 28 '17 at 16:54
  • 2
    $\begingroup$ @D.W. We don't really need that assumption since unset levers just correspond to unspecified variables. The existence of a satisfying assignment doesn't change, and we can assign true/false arbitrarily to get a concrete assignment. $\endgroup$ – Tomoki Jul 28 '17 at 17:16
  • 1
    $\begingroup$ @D.W I don´t know why the order of the pulled/pushed levers matters. Once we defuse a bomb, that bomb stays defused. Even if the counter gets to zero a deffused bomb doesn´t explode. Also there are at most three green and three red cables for each bomb, if we don´t activate a red wire inside the bomb, that means that the bomb can only we decremented by two at most, so that means that the bomb can´t explode. Also we can only pull or push the levers once. At least that´s the way I understood the question. I might be wrong, though $\endgroup$ – rotia Jul 29 '17 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.