1 citations · 1 across the 13 of their papers we have counts for
10 papers · 1 filter
Linked Fates: How Small of an Ambiguity Increase Can Make the Difference Between Equaling and Separating from P?
Benjamin Carleton, Michael C. Chavrimootoo, Lane A. Hemaspaandra +3
Ambiguity-bounded versions of , denoted , bound by the number of accepting paths the nondeterministic polynomial-time Turing machine ca…
Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
Michael C. Chavrimootoo, Jin Seok Youn
The Hanano Puzzle is a one-player game with gravity, where the goal is to make colored blocks make contact with flowers of the corresponding color. The game Jelly no Puzzle shares…
A Brief Note on a Recent Claim About NP-Hard Problems and BQP
Michael C. Chavrimootoo
This short note outlines some of the issues in Czerwinski's paper [Cze23] claiming that NP-hard problems are not in BQP. We outline one major issue and two minor issues, and conclu…
On Czerwinski's " relative to a -complete oracle"
Michael C. Chavrimootoo, Tran Duy Anh Le, Michael P. Reidy +1
In this paper, we take a closer look at Czerwinski's " relative to a -complete oracle" [Cze23]. There are (uncountably) infinitely-many relativized wo…
Evaluating the Claims of "SAT Requires Exhaustive Search"
Michael C. Chavrimootoo, Yumeng He, Matan Kotler-Berkowitz +2
In this paper, we take a closer look at the claims made by Xu and Zhou in their paper "SAT Requires Exhaustive Search" [XZ23], which claims to provide a lower bound on the complexi…
A Closer Look at Some Recent Proof Compression-Related Claims
Michael C. Chavrimootoo, Ethan Ferland, Erin Gibson +1
Gordeev and Haeusler [GH19] claim that each tautology of minimal propositional logic can be proved with a natural deduction of size polynomial in . This builds on work fro…
A Critique of Sopin's ""
Michael C. Chavrimootoo, Ian Clingerman, Quan Luu
We critique Valerii Sopin's paper "" [Sop14]. The paper claims to resolve one of the major open problems of theoretical computer science by leveraging the…
Defying Gravity: The Complexity of the Hanano Puzzle
Michael C. Chavrimootoo
Using the notion of visibility representations, our paper establishes a new property of instances of the Nondeterministic Constraint Logic (NCL) problem (a PSPACE-complete problem…
A Critique of Kumar's "Necessary and Sufficient Condition for Satisfiability of a Boolean Formula in CNF and Its Implications on P versus NP problem."
Michael C. Chavrimootoo, Henry B. Welles
In this paper, we analyze the argument made by Kumar in the technical report "Necessary and Sufficient Condition for Satisfiability of a Boolean Formula in CNF and Its Implications…
A Critique of Keum-Bae Cho's Proof that
Benjamin Carleton, Michael C. Chavrimootoo, Conor Taliancich
In this paper we critique Keum-Bae Cho's proof that . This proof relates instances of 3-SAT to indistinguishable binomial decision trees and clai…