• @rockSlayer
    link
    41 year ago

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

    • Christian
      link
      fedilink
      11 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
        link
        01 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