Cheraghchi, Mahdi; Hirahara, Shuichi; Myrisiotis, Dimitrios; Yoshida, Yuichi One-tape Turing machine and branching program lower bounds for MCSP. (English) Zbl 07922396 Theory Comput. Syst. 68, No. 4, 868-899 (2024). MSC: 68Qxx 94Cxx 03Dxx × Cite Format Result Cite Review PDF Full Text: DOI
Maass, Wolfgang Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines. (English) Zbl 0608.03013 Trans. Am. Math. Soc. 292, 675-693 (1985). Reviewer: D.Yu.Grigoryev MSC: 03D15 03D10 68Q25 68Q05 68Q45 × Cite Format Result Cite Review PDF Full Text: DOI