• Christian@lemmy.ml
    link
    fedilink
    arrow-up
    1
    ·
    1 year ago

    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.

    • rockSlayer@lemmy.world
      link
      fedilink
      arrow-up
      1
      ·
      1 year ago

      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