<p>I want to know the time complexity of the fastest algorithm for solving AM <span class="math-container">$\cap$</span> coAM, but I haven't found any relevant literature. For example, are there any problems that are complete problems in AM <span class="math-container">$\cap$</span> coAM?</p>

CC BY-SA 4.0
2024-09-17T06:06:05.750Z
Very likely, there are no complete problems for AM $\cap$ coAM, and there are problems in this class, or even in NP $\cap$ coNP, that require exponential time to solve. None of this has been proven.
Emil Jeřábek
CC BY-SA 4.0
2024-09-17T08:42:11.433Z
Thanks for your answers! @Emil Jeřábek
constantine
<cc.complexity-theory><reference-request><complexity-classes>
What is the time complexity of the fastest algorithm for solving AM $\cap$ coAM?
constantine
# What is the time complexity of the fastest algorithm for solving AM $\cap$ coAM?

(Asked by: username_0 on 2024-09-17)

I want to know the time complexity of the fastest algorithm for solving AM $\cap$ coAM, but I haven't found any relevant literature. For example, are there any problems that are complete problems in AM $\cap$ coAM?

**Tags:** cc.complexity-theory, reference-request, complexity-classes

> **Comments:**
> **username_1**: Very likely, there are no complete problems for AM $\cap$ coAM, and there are problems in this class, or even in NP $\cap$ coNP, that require exponential time to solve. None of this has been proven.  
> **username_0**: Thanks for your answers! @username_1  

---

## 0 answers

