文章基本信息

标题：Encodings and the Tree Evaluation Problem
本地全文：下载
作者：James Cook ; Ian Mertz
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that the Tree Evaluation Problem with alphabet size k and height h can be solved by branching programs of size kO(hlogh)+2O(h) . This answers a longstanding challenge of Cook et al. (2009) and gives the first general upper bound since the problem's inception.
关键词：Catalytic Computation;space complexity;tree evaluation problem