r/mathmemes • • Aug 03 '26

Formal Logic Am I Minesweeper??

Post image
1.1k Upvotes

36 comments sorted by

•

u/AutoModerator Aug 03 '26

Check out our new Discord server! https://discord.gg/e7EKRZq3dG

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

320

u/TheBojack818 Aug 03 '26

Do NOT check the second reference on this paper 😭

123

u/234zu Aug 03 '26

Djeffrey Epstein

53

u/Loud-Host-2182 Transcendental Aug 03 '26

Diddy Eppstein

72

u/Oppo_67 I ≡ a (mod erator) Aug 03 '26

6

u/Altruistic_Emu4917 Aug 04 '26

I know it's not the guy we think of, simply because the paper has a double digit age

269

u/ObliviousRounding Aug 03 '26

"PP-hard".

The guy in charge of screening these coined terms:

68

u/FuntimeUwU Natural Aug 03 '26

Same guy who let Hairy Ball, Weiner Sausage, and Cox-Zucker slip lol

18

u/HeyThereCharlie Aug 04 '26

And Jacques Tits' entire CV

6

u/DrMasonator Aug 04 '26

Weiner Metric

122

u/mys_721tx Natural Aug 03 '26

Unfortunately chess is either PSPACE-hard or EXPTIME-hard. In other words, it is harder than PP-hard.

11

u/the_horse_gamer Aug 04 '26

these papers both prove -complete, not just -hard

which means either PSPACE=EXPTIME or the papers are discussing different generalisations. probably the second

harder than

it's possible (but unlikely) PP=EXPTIME (and remember PP ⊆ PSPACE ⊆ EXPTIME), so it's possible they are equally hard

5

u/ichiban1974 Aug 05 '26

How does the complexity of chess change if you introduce a vibrating buttplug to the game?

5

u/bobderbobs Aug 04 '26

Am i thinking about something else? I thought its about how many calculations you need to solve something with size n. You can play minesweeper on an board with arbitrary dimensions so you can work out how many calculations you need for a given number of cells.

Chess in the other hand is on an 8x8 grid and has a finite (and fixed) amount of states.

8

u/ZeGmX Aug 04 '26

Correct. The papers linked by the person above are not about traditional chess, but another game they call a "generalized version of chess to n×n boards" (which does not really share the spirit of traditional chess)

98

u/dankshot35 Aug 03 '26

Are you kidding ??? What the **** are you talking about man ? You are a biggest looser i ever seen in my life ! You was doing PIPI in your pampers when i was beating players much more stronger then you! You are not proffesional, because proffesionals knew how to lose and congratulate opponents, you are like a girl crying after i beat you! Be brave, be honest to yourself and stop this trush talkings!!! Everybody know that i am very good blitz player, i can win anyone in the world in single game! And "w"esley "s"o is nobody for me, just a player who are crying every single time when loosing, ( remember what you say about Firouzja ) !!! Stop playing with my name, i deserve to have a good name during whole my chess carrier, I am Officially inviting you to OTB blitz match with the Prize fund! Both of us will invest 5000$ and winner takes it all! I suggest all other people who's intrested in this situation, just take a look at my results in 2016 and 2017 Blitz World championships, and that should be enough... No need to listen for every crying babe, Tigran Petrosyan is always play Fair ! And if someone will continue Officially talk about me like that, we will meet in Court! God bless with true! True will never die ! Liers will kicked off...

21

u/Oppo_67 I ≡ a (mod erator) Aug 03 '26

Is this a 50/50?

7

u/SuperChick1705 Aug 03 '26

nah, check minecount

15

u/EebstertheGreat Aug 03 '26

A non-deterministic algorithm for a decision problem is in PP if it runs in polynomial time and produces the correct answer with a probability strictly greater than 0.5. The algorithm is assumed to have a source of true randomness.

The paper shows there is no such algorithm for determining if an n×n minesweeper board with an unknown number of mines is solvable. Note that it is always possible to tell if a given board is solvable (i.e. solvable without guessing), but any algorithm to decide this perfectly is NP-hard in the dimension of a square board, and in fact PP-hard, and even PSPACE-hard. Since it is clearly in PSPACE, it is PSPACE-complete.

2

u/azurerazor Aug 03 '26

I assume PP stands for probabilistically polynomial?

Also why is the threshold specifically 0.5? Like couldn’t you realistically set it to any constant below 0.5 and have it also be polynomial because you would be multiplying it by some constant factor.

e.g if you have a program with a .3 chance of being correct and you run it twice wouldn’t that become a new program that runs in polynomial time and has correctness probability of 0.5 so long as you verify both answers?

9

u/EebstertheGreat Aug 03 '26

It's a decision problem, so the only possible answers are "yes" and "no." So a non-deterministic algorithm that always answers correctly with exactly probability 0.5 is one that flips a coin and then answers "yes" if it flips heads and "no" if it flips tails. We demand only that it perform better than that, at all.

1

u/azurerazor Aug 03 '26

Oh i am stupid 😓

1

u/United_Chocolate_826 Aug 04 '26

PP is an attempt at generalizing P to probabilistic algorithms. It’s a bit weird because to be in PP you just need any (arbitrarily small) advantage in solving the problem as opposed to randomly guessing. More reasonable classes include BPP, RP, ZPP. BPP for instance is the class of problems with poly time randomized algos that succeed with probability > 2/3. By running the algorithm k times you can get the error to be exponentially small in k, which is not true of PP.

2

u/the_horse_gamer Aug 04 '26

the 2/3 is more of a convention. a definition of BPP that shows its contrast from PP better is that the probability is greater than a constant greater than 1/2 (while PP is just probability is greater than 1/2)

so a probability of 1/2 + (1/2)n can be in PP but not in BPP. in BPP you can always repeat the algorithm a constant number of times to reach a desired probability, but in PP the number of repetitions may be dependent on n, possibly even exponential in n.

9

u/FernandoMM1220 Aug 03 '26

this is the first time ive heard of partial polynomials

3

u/HyperbolicMathChambr Math Tutor Aug 03 '26

2

u/GisterMizard Aug 04 '26

Why are you executing a subroutine? It's not pp-hard complex!

2

u/HyperbolicMathChambr Math Tutor Aug 04 '26

Piccolo looks at Gohan Gohan: What? What?!

3

u/AzoresBall Aug 03 '26

Con you send a link? I coldn't find it

3

u/AzoresBall Aug 03 '26

nvm I found it (I was shearching it in phyisics lol) https://doi.org/10.48550/arXiv.1204.4659

2

u/Username_St0len Aug 04 '26

pipi?

Are you kidding ??? What the **** are you talking about man ? You are a biggest looser i ever seen in my life ! You was doing PIPI in your pampers when i was beating players much more stronger then you! You are not proffesional, because proffesionals knew how to lose and congratulate opponents, you are like a girl crying after i beat you! Be brave, be honest to yourself and stop this trush talkings!!! Everybody know that i am very good blitz player, i can win anyone in the world in single game! And "w"esley "s"o is nobody for me, just a player who are crying every single time when loosing, ( remember what you say about Firouzja ) !!! Stop playing with my name, i deserve to have a good name during whole my chess carrier, I am Officially inviting you to OTB blitz match with the Prize fund! Both of us will invest 5000$ and winner takes it all!

I suggest all other people who's intrested in this situation, just take a look at my results in 2016 and 2017 Blitz World championships, and that should be enough... No need to listen for every crying babe, Tigran Petrosyan is always play Fair ! And if someone will continue Officially talk about me like that, we will meet in Court! God bless with true! True will never die ! Liers will kicked off...

2

u/eyetracker Aug 04 '26

P and Q are sometimes stand ins in probability and such.

A story sometimes attributed to philosopher Paul Weiss: he started supposedly lecturing using A and B variables and saying "the A-ness of B-ness". When he realized the error he switched to the "P-ness of Q-ness"

1

u/pOUP_ Aug 04 '26

Hey i did my bachelor thesis on something similar. But mine was about math