coja@lemmy.ml to Programmer Humor@lemmy.ml · 1 year agoEarly disappointmentlemmy.mlimagemessage-square91fedilinkarrow-up11.11Karrow-down119
arrow-up11.09Karrow-down1imageEarly disappointmentlemmy.mlcoja@lemmy.ml to Programmer Humor@lemmy.ml · 1 year agomessage-square91fedilink
minus-squareChristian@lemmy.mllinkfedilinkarrow-up1·1 year 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.worldlinkfedilinkarrow-up1arrow-down1·1 year 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
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