Når vi har to eller flere akseptable veier i en ikke-deterministisk maskin, hvilken velger vi og hvilke kriterier kan vi bruke?
Mandag, 16 oktober 2023
by panosadrianos
I området for beregningskompleksitetsteori, spesielt i studiet av endelige tilstandsmaskiner, spiller begrepet ikke-determinisme en viktig rolle. Ikke-deterministiske endelige tilstandsmaskiner (NFSM) er teoretiske modeller som gjør det mulig å ta flere akseptable veier i en gitt tilstand. Men når man står overfor en slik situasjon, oppstår spørsmålet: hvilken