Resumen

Uno de los métodos conocidos para resolver problemas con una complejidad temporal exponencial, como los problemas NP-completos, es el uso de algoritmos de fuerza bruta. Recientemente, se ha introducido un nuevo marco computacional paralelo llamado Computación de Membrana que puede aplicarse a los algoritmos de fuerza bruta. La forma habitual de encontrar una solución para los problemas con complejidad de tiempo exponencial con técnicas de Computación de Membrana es mediante el Sistema P con membrana activa utilizando la regla de división. Se hace un espacio de trabajo exponencial y se resuelven los problemas con complejidad exponencial en un tiempo polinómico (incluso lineal). Por otro lado, la búsqueda es actualmente uno de los métodos más utilizados para encontrar solución a problemas en la vida real, que los algoritmos de búsqueda ciega son precisos, pero su complejidad temporal es exponencial como el algoritmo breadth-first search (BFS). En este trabajo, proponemos un nuevo enfoque para la implementación de BFS utilizando por primera vez el sistema P con la técnica de regla de división. El teorema muestra que la complejidad temporal de BSF en este marco en árboles binarios aleatorios se reduce de O(2d) a O(d).

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:algoritmos de fuerza bruta, complejidad temporal exponencial, problemas, complejidad temporal, nuevo marco computacional paralelo, técnicas computacionales de membrana, algoritmos de búsqueda ciega, técnica de reglas de división, árboles binarios aleatorios, bfs
• Keywords:brute force algorithms, exponential time complexity, problems, time complexity, new parallel computational framework, membrane computing techniques, blind search algorithms, division rule technique, randomly binary trees, bfs