Generalized shogi and chess are constant-time tastable
Generalized shogi and chess are constant-time tastable
复制标题
广义将棋和国际象棋是恒定时间可品尝的
DOI：
10.1049/cp.2015.0601
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
and Teagun Park
中科院分区：
文献类型：
--
作者：
Hiro Ito;Atsuki Nagao;and Teagun Park
我们提出了恒定的时间测试算法的广义将棋（日本象棋）和国际象棋。这些问题被称为EXPTIME-完全问题。属性的测试算法（或测试器）如果具有该属性则接受输入，如果它远离高概率具有该属性则拒绝它（例如，至少2/3），只阅读输入的恒定部分。如果存在测试者，则属性被称为可测试的。广义将棋（和国际象棋）问题是，给定n × n棋盘上的任何位置，O（n）个棋子，用于测试“先移动的玩家有获胜策略”的属性。我们提出，这个属性是可测试的将棋和国际象棋。将棋测试是片面的错误和国际象棋测试是令人惊讶的没有错误！在过去的十年中，许多问题被发现是可测试的。然而，几乎所有这些问题都属于NP类。这是关于EXPTIME-完全问题的常数时间可测性的第一个结果。
We present constant-time testing algorithms for the generalized shogi (Japanese chess) and chess. These problems are known to be EXPTIME-complete. A testing algorithm (or a tester) for a property accepts an input if it has the property and rejects it if it's far from having the property in high probability (e.g., at least 2/3) by reading only a constant part of the input. A property is said to be testable if there is a tester. The generalized shogi (and chess) problem is, given any position on √n x √n board with O(n) pieces, for testing the property “the player who moves first has a winning strategy.” We present that this property is testable for both shogi and chess. The shogi tester is one-sidederror and the chess tester is surprisingly no-error! In the last decade, many problems have been found to be testable. However, almost all of such problems are in class NP. This is the first result on constant-time testability of EXPTIME-complete problems.