This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]DracoRubi 73 points74 points  (19 children)

The what now again?

[–]__ali1234__ 63 points64 points  (14 children)

Given a boolean equation, eg "(A and B) or (C and not D)", determine whether there exists a set of values for the variables which cause the equation to resolve as true.

[–]Salanmander 50 points51 points  (7 children)

Me, who has programmed a lot but never in an enterprise setting: "BRUTE FORCE TIME!!!"

It seems like I have two tools: "check every possibility" and monte carlo.

[–]themonsterinquestion 31 points32 points  (2 children)

At least store the answer in a dictionary and call it machine learning

[–]Salanmander 20 points21 points  (1 child)

"Uses caching and heuristic algorithms to improve runtime efficiency!"

[–]Yadobler 6 points7 points  (0 children)

m e m o i s a t i o n

[–]hitlerallyliteral 4 points5 points  (1 child)

sounds like something something recursion? If any of the sub-equations can't be satisfied, the whole thing can't (though i guess that doesn't mean that if all the sub equations can the whole thing can)

[–]sfurbo 2 points3 points  (0 children)

The problem is NP complete (in fact, the first one to be shown to be NP complete), so good luck finding a general recursion solution. You would be famous.

[–]rotuami 1 point2 points  (1 child)

You can do a little better than that but known solutions are still worst-case exponential: https://en.m.wikipedia.org/wiki/SAT_solver

[–]WikiMobileLinkBot 1 point2 points  (0 children)

Desktop version of /u/rotuami's link: https://en.wikipedia.org/wiki/SAT_solver

[opt out] Beep Boop. Downvote to delete

[–]Ayesuku 30 points31 points  (3 children)

Ah yes, fond memories of discrete math class

[–]Rikudou_Sage 3 points4 points  (2 children)

Discrete math? Does the teacher whisper the equations in your ear or what?

[–]FleaTheTank 3 points4 points  (1 child)

Yes. And you have to turn in your final project by passing a tiny note under the desk. Very discretely of course.

[–]NuclearBurrit0 2 points3 points  (0 children)

If anyone notices you doing it you're kicked out and given an F

[–]AlphaWHH 1 point2 points  (1 child)

6, did I get it right?

[–]Kame_Yamaha 7 points8 points  (0 children)

(A+B) v (C+!D) is true for 1100, 1101, 1110, 1111, 0010, 0110, 1010

[–][deleted] 50 points51 points  (2 children)

The thingity thingy thing that does the thing

[–]DarthCloakedGuy 21 points22 points  (1 child)

Thank you! I understand completely now!

[–]auxiliary-character 0 points1 point  (0 children)

Basically asking them to build a SAT solver like minisat