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

    Nondeterministic turing machines are the same kind of impossible theoretical automaton as an NFA. They can theoretically solve NP problems.

    • 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
        arrow-down
        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