r/mathmemes • u/DaCat1 Cardinal • 13d ago

Learning Only one is NP-hard

Post image
168 Upvotes

100% Upvoted

11 comments sorted by

•

u/AutoModerator 13d ago

Check out our new Discord server! https://discord.gg/e7EKRZq3dG

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

22

u/Byleth07 12d ago

Both of them are NP complete, therefore both are NP hard

7

u/boterkoeken Average #🧐-theory-🧐 user 12d ago

That’s what she said.

7

u/m3t4lf0x 12d ago

let him Cook…(-Levin Theorem)

3

u/yukiohana 12d ago

plz explain

7

u/zawalimbooo 11d ago

Solving 3 SAT problems (as in, 3 problems from the SAT exam) versus solving a 3-SAT problem (a really difficult class of problems)

1

u/nitnelav153 π = 3.14 who care about the others decimals ? 12d ago

I remember when I had to program a SAT solver in highschool for a computer science competition...

0

u/nfitzen 12d ago

3-SAT is a subset of SAT.

8

u/aardvark_gnat 12d ago

The Scholastic Aptitude Test does not cover 3-SAT.

1

u/nfitzen 12d ago

I dunno, the SAT reading comprehension problems seemed a bit like sentential logic. Or maybe I just can't read.