Verification versus Search in Labeled Subcube Partitions: Exact Small-Width Bounds

Abstract

The paper studies M(k), the maximum decision-tree complexity of a total unique search problem with witness size at most k, and determines the exact values M(1)=1, M(2)=2, M(3)=4 and M(4)=5 with a computer-assisted upper bound for width four.