Separation and Collapse of Equilibria Inequalities on AND-OR Trees without Shape Constraints

Fuki Ito, Toshio Suzuki

Herein, we investigate the zero-error randomized complexity, which is the least cost against the worst input, of AND-OR tree computation by imposing various restrictions on the alg…