1.1K

Early disappointment(lemmy.ml)

posted
by
Avatar
coja@lemmy.ml
in
Avatar
programmerhumor@lemmy.ml
92 comments
hidereport
Sort:
HotTopControversialNewOld
You are viewing a single thread.
View all comments View context
Avatar
rockSlayer@lemmy.world
4 points

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

permalink
report
parent
reply
Avatar
Christian@lemmy.ml
1 point

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.

permalink
report
parent
reply
Avatar
rockSlayer@lemmy.world
0 points

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

permalink
report
parent
reply

Programmer Humor

!programmerhumor@lemmy.ml

Create 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.

Community stats

  • 5.3K

    Monthly active users

  • 1.5K

    Posts

  • 33K

    Comments

Community moderators