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

Christian
link
fedilink
11Y

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

Create a post

Post funny things about programming here! (Or just rant about your favourite programming language.)

Rules:

  • Posts must be relevant to programming, programmers, or computer science.
  • No NSFW content.
  • Jokes must be in good taste. No hate speech, bigotry, etc.
  • 1 user online
  • 61 users / day
  • 247 users / week
  • 417 users / month
  • 2.88K users / 6 months
  • 1 subscriber
  • 1.53K Posts
  • 33.9K Comments
  • Modlog