Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-

P vs NP

Name: Anonymous 2006-10-21 3:27

In the application of minesweeper, am I right to say that the goal in solving P vs NP is to formulate an algorithm that determines if the board is logical (possible) in layout where n is the number of blocks:

c*n^k

instead of a calculation time of
n! or c^n ?

Name: Anonymous 2006-10-21 14:53

More like c*n^k/0

Name: Anonymous 2006-10-22 6:42 (sage)

>>1
Well, for the special case of Minesweeper, yes. Since you have a polynomial-time method of checking a solution (just check all the clicks for bombs), you need a polynomial time algorithm to find it.

To solve P vs NP, you need to show that this works in general, or give a counterexample.

Name: Anonymous 2006-10-24 5:25

If you can solve it you get $1 million. Get cracking.

Name: Anonymous 2006-10-24 10:52

Just use deduction until you cannot deduce any mroe certainties then calculate the highest probability of getting a square right.

Don't change these.
Name: Email:
Entire Thread Thread List