Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ONE-TAPE TURING MACHINES:
Reports tagged with One-Tape Turing Machines:
TR20-103 | 9th July 2020
Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida

#### One-Tape Turing Machine and Branching Program Lower Bounds for MCSP

Revisions: 1

For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{0,1\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) is at most a threshold $s(n)$. A ... more >>>

ISSN 1433-8092 | Imprint