Problemas en la mañana o en la mañana

¿Cuáles son los ejemplos de problemas conocidos en (resp. ) que no se sabe que están en ni en ?M A N P B P $\mathsf{AM}$$\mathsf{MA}$$\mathsf{NP}$$\mathsf{BPP}$

Para , conozco los siguientes dos ejemplos:$\mathsf{AM}$

• No isomorfismo gráfico: dados dos gráficos etiquetados y , ¿son el mismo gráfico hasta la permutación de los vértices?$G$$H$
• Protocolo de límite inferior: se le proporciona un conjunto tal manera que sabe queopara algunos , y tal que S \ in \ mathsf {AM} (es decir, dado y \ en U , verificando si y \ in S puede resolverse en \ mathsf {AM} ), y tienes que decidir si | S \ ge 4 \ alpha | U | .| S | ≤ α | U | El | S | ≥ 4 α | U | 0 ≤ α ≤ 1 S ∈ A M y ∈ U y ∈ S A M | S ≥ 4 α | U $S\subset\{0,1\}^m$$|S|\le\alpha|U|$$|S|\ge 4\alpha|U|$$0\le\alpha\le 1$$S\in\mathsf{AM}$$y\in U$$y\in S$$\mathsf{AM}$$|S\ge 4\alpha|U|$

Para $\mathsf{MA}$ , no conozco ningún ejemplo.

Mi pregunta refinada: ¿Conocemos otros problemas en $\mathsf{AM}$ o $\mathsf{MA}$ , que no se sabe que están en $\mathsf{NP}\cup\mathsf{BPP}$ ?

No me interesan los problemas para los cuales la única prueba de que pertenecen a es mediante el uso de uno de estos dos protocolos.$\mathsf{AM}$

Editar: Mi principal motivación es poder dar ejemplos de algoritmos o para explicar cuáles son estas clases.$\mathsf{AM}$$\mathsf{MA}$

[Estoy publicando esto como respuesta a pesar de estar en porque a) exhibe un tipo diferente de algoritmo de estilo M A , yb) @PeterShor preguntó y fue demasiado largo para un comentario .]$\mathsf{PromiseMA}$$\mathsf{MA}$

Sobre cualquier campo finito , el siguiente problema está en P r o m i s e M A :$\mathbb{F}$$\mathsf{PromiseMA}$

Entrada : Un conjunto de -polynomials F 1 ( → x ) , ... , F m ( → x$\mathbb{F}$$F_1(\vec{x}), \dotsc, F_m(\vec{x})$

Decida : ¿No hay solución para sobre el cierre algebraico ¯ $F_1(\vec{x}) = \dotsb = F_m(\vec{x}) = 0$$\overline{\mathbb{F}}$

Promesa : O hay una solución sobre , o hay un circuito algebraico F de polietileno C ( → x , y 1 , ... , y m ) tal que C ( → x , → 0 ) = 0 y C ( → x , → F ( → x ) ) = 1 (idénticamente como polinomios)$\overline{\mathbb{F}}$ $\mathbb{F}$$C(\vec{x}, y_1, \dotsc, y_m)$$C(\vec{x}, \vec{0}) = 0$$C(\vec{x}, \vec{F}(\vec{x})) = 1$

El algoritmo de estilo adivina el circuito C y, a continuación, verifica las dos condiciones utilizando pruebas de identidad polinomio, que está en c o R P por Schwarz-Zippell-DeMillo-Lipton.$\mathsf{MA}$$C$$\mathsf{coRP}$

Tenga en cuenta que, sin la restricción del tamaño de polietileno, Nullstellensatz de Hilbert garantiza que no hay solución si y solo si hay algún circuito satisfaga las dos condiciones anteriores. (Por otro lado, suponiendo que N P ⊈ c o M A , existen sistemas de ecuaciones que provienen de algebrizaciones de 3SAT para las cuales se viola la promesa de tamaño polivinílico anterior).$C$$\mathsf{NP} \not\subseteq \mathsf{coMA}$

(Esta es la base de un sistema de prueba algebraico de un trabajo conjunto reciente con Toniann Pitassi , pero para los propósitos de esta respuesta, ideas similares se remontan a un documento anterior de Pitassi, así como a su charla ICM de 1998 , y al llamado Nullstellensatz y sistemas de prueba de cálculo polinomial .)