Juan Lopes @juanlopes.dev · Dec 22 Sim, na minha monografia fiz uma implementação de 3SAT usando "expressões regulares" com backreferences. São NP-completas.
5 likes 1 replies
?
Replies
AFAIK expressões µ-regular são equivalentes Turing-completos, precisa só de muito malabarismo. Isso vem de que autômatos de fila são equivalentes a máquinas de Turing e o backreference permite justamente processar filas. É mais poderoso do que "apenas" NP-completo