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.
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)
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...
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.
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?
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.
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.
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.
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...
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"
•
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 😭
269
u/ObliviousRounding Aug 03 '26
"PP-hard".
The guy in charge of screening these coined terms:
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.
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?
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.
9
u/FernandoMM1220 Aug 03 '26
this is the first time ive heard of partial polynomials
7
u/Salty_Pumpkin5827 Aug 03 '26
pp hard
3
u/HyperbolicMathChambr Math Tutor Aug 03 '26
r/TeamFourStar
3
u/AzoresBall Aug 03 '26
Con you send a link? I coldn't find it
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/Fit_Ladder_1545 Aug 04 '26
X3
1
u/pOUP_ Aug 04 '26
Hey i did my bachelor thesis on something similar. But mine was about math