Masao Hara
ABSTRACT
Hass, Lagarias, and Pippenger analyzed the computational complexity of various decision problems in knot theory. They proved that the problem whether a given knot is unknotting is in NP, and conjectured that the problem is contained in NP∩co-NP. Agol, Hass, and Thurston proved that the problem called ManifoldGenus, which is a general problem of Unknotting, is NP-complete. We construct an interactive proof system for Knotting, and prove that the problem is contained in IP(2). Consequently, Unknotting is contained in AM ∩ co-AM. If Unknotting is NP-complete, then Σ2p = Π2p.
- Unknotting is in AM ∩ co-AM
Recommendations
Infeasibility of instance compression and succinct PCPs for NP
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingThe OR-SAT problem asks, given Boolean formulae Φ1,...,Φm each of size at most n, whether at least one of the Φi's is satisfiable. We show that there is no reduction from OR-SAT to any set A where the length of the output is bounded by a polynomial in n,...
Impossibility results on weakly black-box hardness amplification
FCT'07: Proceedings of the 16th international conference on Fundamentals of Computation TheoryWe study the task of hardness amplification which transforms a hard function into a harder one. It is known that in a high complexity class such as exponential time, one can convert worst-case hardness into average-case hardness. However, in a lower ...
Infeasibility of instance compression and succinct PCPs for NP
The OR-SAT problem asks, given Boolean formulae @f"1,...,@f"m each of size at most n, whether at least one of the @f"i's is satisfiable. We show that there is no reduction from OR-SAT to any set A where the length of the output is bounded by a ...
Comments