Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Bonus Challenge: Proof that Formula-to-DNF conversion is NP-hard
Now that Problem 8.2 has been scrapped, I would instead like to give you the opportunity to earn some bonus bonus points over the holiday.
NP-hardness of Formula-to-DNF follows immediately if we can find a formula phi whose minimal equivalent DNF is exponential in the length of phi. Such a formula and proof that its minimal equivalent DNF is exponential in its input length is provided here:
30 Bonus Bonus Points to the first three people who explain the proof to me ;).
Rules
You may only work on this challenge alone. I will be back in the office from January 19th, hence that is the earliest possible date for a submission. On that day or thereafter come to my office (write me an email beforehand if you want to be sure to encounter me).
Bonus Bonus Points are added to your Bonus Points but do not count towards the total of achievable bonus points:
ratio of bonus points = min((bonus points+bonus bonus points)/bonus points,1)
In other words you can make up for missed bonus points but not get more than 100% of the bonus points.
Be warned, I don’t usually know the solution to a challenge so their difficulty may range from trivial to impossible or the question may not even be well-defined. In that case, if you provide a good explanation why the problem is hard/impossible, I may still give you the bonus points.