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

In reply to Re^4: Challenge: Optimal Bagels Strategy by ELISHEVA
in thread Challenge: Optimal Bagels Strategy by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.