Resolución de alunos problemas de álgebra lineal a través de algoritmos no deterministas

Abstract

Resumen En este trabajo especial de grado se presentan 4 problemas matriciales asociados al rango y al determinante, de donde se muestran clasificaciones de los mismos dependiendo del conjunto a considerar; y la clasificación se realiza en términos del tiempo de resolución a través de algoritmos probabilísticos, o mostrando que no existe algoritmo capaz de resolverlo. Para esto se desarrollan los algoritmos pertinentes al problema, o mediante el uso de propiedades de varios problemas de decisión conocidos y reducciones entre problemas de decisión se muestra una equivalente entre distintos problemas; para algunos de los resultados haremos uso de la teoría existencial de primer orden para sus demostraciones. Palabras claves:matrices, problemas de decisión, algoritmos, clasificación, reducción de problemas.