coja to Programmer Humor · 1 year agoEarly disappointmentimagemessage-square89fedilinkarrow-up11.12Karrow-down119
arrow-up11.1Karrow-down1imageEarly disappointmentcoja to Programmer Humor · 1 year agomessage-square89fedilink
minus-squarerockSlayer@lemmy.worldcakelinkfedilinkarrow-up6arrow-down2·1 year agoNondeterministic turing machines are the same kind of impossible theoretical automaton as an NFA. They can theoretically solve NP problems.
minus-squareChristianlinkfedilinkarrow-up1·11 months agoIt’s been a long long time since I touched this but I’m still almost positive deterministic machines can solve everything in NP already.
minus-squarerockSlayer@lemmy.worldcakelinkfedilinkarrow-up1arrow-down1·11 months agoThey exist in the same grammatical hierarchy so theoretically they can solve the same problems. What I should have said was that nondeterministic turing machines can solve NP problems in P
Nondeterministic turing machines are the same kind of impossible theoretical automaton as an NFA. They can theoretically solve NP problems.
It’s been a long long time since I touched this but I’m still almost positive deterministic machines can solve everything in NP already.
They exist in the same grammatical hierarchy so theoretically they can solve the same problems. What I should have said was that nondeterministic turing machines can solve NP problems in P