Some combinatorial game problems require Ω( n k ) time
From MaRDI portal
Publication:3768395
DOI10.1145/62.322433zbMath0631.68036OpenAlexW2064968744MaRDI QIDQ3768395
Shigeki Iwata, Akeo Adachi, Takumi Kasai
Publication date: 1984
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/62.322433
Related Items
Gradually intractable problems and nondeterministic log-space lower bounds, Complexity, appeal and challenges of combinatorial games, Simultaneous (poly-time, log-space) lower bounds, From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability, On the complexity of deciding fair termination of probabilistic concurrent finite-state programs, Fine-grained Lower Bounds on Cops and Robbers, The complexity of pursuit on a graph, A multiparameter analysis of domino tiling with an application to concurrent systems, Complexity of path-forming games, Verifying whether one-tape Turing machines run in linear time, Pursuing a fast robber on a graph, Recent results and questions in combinatorial game complexities
