in reply to Challenge: Optimal Bagels Strategy

Increasing the possible values of $v has a minimal effect on the computational complexity of this problem. For any given value of $v "colors" and $p colors per solution, this puzzle can always be solved with a maximum of ceiling($v/$p)-1+ $p! guesses. The total number of permutations possible for a particular value of $v and $p has no impact.

In the original bagel problem we have $p=3 and $v=10. Although there are 648 possible 3 digit permutations, according to this formula, the maximum number of guesses is never more than 9:

  ceiling($v/$p)=ceiling(10/3)=4
  $p! = 3*2*1 = 6

  #so... 
  ceiling($v/$p)-1 + $p! = 3 + 6
  = 9

[download]

If we increase $v to its maximum proposed value, 36, we only add 8 more guesses ceiling($v/$p) only increases from 4 to 12. On the other hand if we increase $p to its maximum of 10, then the maximum number of guesses becomes ~ 10! or about 3.6 million.

  ceiling($v/$p)=ceiling(36/10) = 4
  $p! = 10!
  #so...
  ceiling($v/$p)-1 + p! = 3 + 10!

[download]

My gut sense is that this puzzle is NP complete within solution space defined by ceiling($v/$p)-1+p!. That is, we have indeed exhausted all the information available if we following the guessing strategy that led to that formula. You can come up with fewer guesses than that by sheer chance and a smart use of what chance gives you. For example, clever use of information from an initial guess whose response is $p-2 fermi and 2 pico can be solved much more quickly than a puzzle whose initial $p guesses are 1 pico each. If the luck of the draw gives you such an initial set of guesses, you can't use any sort of logic to ensure that your number of guesses will be less than ceiling($v/$p)-1+p!.

Of course, all of this assumes that the maximum number of guesses really is ceiling($v/$p)-1+ $p!. The formula is based on the algorithm described below. I haven't converted it into code because I wanted to focus on explaining the logic, but it wouldn't be too difficult to do so. I'm often prone to overlook things when I do this kind of mathematical reasoning so a second pair of eyes for my argument would be much appreciated.

<Reveal this spoiler or all in this thread>

Best, beth

Replies are listed 'Best First'.
Re^2: Challenge: Optimal Bagels Strategy
by ELISHEVA (Prior) on Sep 30, 2009 at 16:50 UTC

    Upon further reflection I'm no longer convinced that this is an NP hard problem, but this may be because I'm a bit fuzzy on the nuances of the definition of NP hard.

    Although the worst case is always proportional to $p!, this problem still isn't as "hard" as a problem where we simply got the number of non-bagels and "yes/no" about whether they were in the right order. If we just got "yes/no" then once we knew all the digits, every additional guess would at most eliminate one of $p! possible permutations. However, in our case we can sometimes know how many are in the right position. Each time we get lucky and make a guess with one additional fermi, we may be able to reduce the number of potential remaining solutions by more than just 1.

    For example, suppose the problem selector chooses a solution that will yield $p-$x fermi and $x pico, on the first guess. The number of follow on guesses needed will always be ($p-1) + ($x-1)!. We need ($p-1) to find the identity of out of order elements and at most ($x-1)! guesses to put the elements in the correct position. We can identify the $x out of place digits by taking a known bagel and replacing each digit in turn. Any guess whose pico count drops by 1 will be replacing an out of order digit. After $p-1 such guesses we will know the identity of all out of place values. To put them in the right order, we need to potentially try all possible orderings where none of the $x elements are in their original position. The first of $x elements may be in ($x-1) locations, the second in any of the ($x-2) remaining and so on. Thus we need to consider ($x-1)! arrangements.

    However, we only need to make ($x-1)! guesses to put things in the right order if the number of pico is $x for all but the final "guess" (the guess we make when we know the answer but have never actually guessed that particular permutation). If after Q guesses we get $y additional fermi, then instead of guessing each remaining ($x-1)! arrangement, the number of remaining guesses is the minimum of ($x-1)! - Q and ($x-1)+($x-$y-1)!.

    However, as I stated earlier, we only have the possibility of making a more informative guess. If "fermis" come late enough in the guessing process we may not be able to use them to reduce the total number of guesses to less than ceiling($v/$p) - 1 + $p!. Some clarification by someone with a firmer understanding of what exactly is meant by NP-hard would be really appreciated so I can use these terms more appropriately.

    Best, beth

[reply]
[d/l]
[select]

      If you are an ACM member, a pretty good description can be found at the beginning of The status of the P versus NP problem, an article in the September 2009 issue of Communications.

      Update: It looks like a free web account (yeah, I know, NYT model) will allow reading of this article. It also looks like the digital edition may allow reading without registration.

      --MidLifeXis

      Please consider supporting my wife as she walks in the 2009 Alzheimer's Walk.

[reply]

        Thanks a lot for the link! I really enjoyed the article. I think what was confusing me was the nature of "hardness" - is it measured by the worst case or the average case? If I understand the article, P and NP refer to the worst case. But many problems present a very different picture if we consider the average case complexity rather than the worst case (see middle of the article).

        Knowing how many are in the right position rather than merely a binary "all in position/one or more out of position" reduces the average complexity, but not the worst-case complexity. If we consider the worst case complexity, both problems (guesses are answered with number in the correct position vs. binary all/one or more) are equally hard and fulfill the definition for NP, but apparently not P ("apparently" because P != NP has not yet been formally proven). It satisfies NP because if we had some sort of miraculous machine that could try all possible guesses at once (i.e. a non-deterministic Turing machine) then we could solve this problem in polynomial time. Verification would be the only step left and to verify a solution we need one equality operation per value, essential O($p). However, it appears to fail P because if we are restricted to a deterministic Turing machine (which can only try possible solutions sequentially), we can't solve this in polynomial time because we have to search the entirety of a solution space that scales according to $p! rather than $p^n for some fixed n. Do I have this right?

        Best, beth

[reply]

In Section Meditations