Bueno, eso es un engañoso título. Este es un poco más sutil problema de pregrado de álgebra lineal, aunque sospecho que todavía hay una respuesta fácil. Pero no pude resistir :D.
Aquí está el verdadero problema: Tenemos una caja negra transformación lineal de $V \rightarrow W$ donde $V, W$ son espacios vectoriales de dimensiones m y n respectivamente (es decir m < n), y queremos saber si tiene rango completo. (Numérico consideraciones no son un problema; si usted quiere, decir que es más de un campo finito.) Esto es fácil de hacer en el tiempo $O(m^2n)$ y con m llama a la caja negra de la función, sólo mediante el cálculo de la imagen de una base de m y usando eliminación Gaussiana. También es obvio que no se puede hacer mejor de lo que m llama a la función en un algoritmo determinista, y estoy bastante seguro, pero no he logrado demostrar que usted no puede vencer a la eliminación Gaussiana asintóticamente.
Pero, ¿podemos hacerlo mejor si queremos un algoritmo probabilístico? Si nos está permitido hacer muchas llamadas a la función como queremos? ¿Cuál es la mejor cota inferior podemos obtener, probabilísticamente? Estos son, probablemente, bastante trivial de preguntas (ya que todo es lineal algebraicas y agradable), pero yo simplemente no saben cómo acercarse a ellos.
