---
id: "2017378987194884179"
created_at: "2026-01-30T23:26:46+00:00"
lang: es
in_reply_to: null
in_reply_to_user: null
thread_root: "2017378987194884179"
kind: original
---

¿Puede toda computación realizada por una máquina de Turing no-determinista en tiempo polinomial ser también realizada por alguna máquina determinista en tiempo polinomial?

O más informalmente: ¿Introducir no-determinismo puede acelerar fundamentalmente la computación?