English subtitles

← 12-01 Preprocessing

Get Embed Code
1 Language

Showing Revision 1 created 10/24/2012 by Amara Bot.

  1. Cleaning the input also known as pre-processing. What's the idea or purpose of that?
  2. Well, the idea is that for many inputs that you're given, so say this is an input
  3. for an NP complete problem, what you would then do having learning the techniques
  4. that I just showed you, you would fire up your search tree of course
  5. until at some point the search tree says, "Bingo! I found a solution for you."
  6. Now, the idea of cleaning the input is to determine if there are certain parts of the input
  7. for which you can already say what the solution will look like without having to go through
  8. the whole search tree so basically something like we saw in the vertex cover
  9. or independent set algorithm where at a certain point in the search tree
  10. we could already say for certain vertices if they were going to be part of that vertex cover
  11. or the independent set without really going into any further branching.
  12. By pre-processing, what you do is you try to find some chunks of the input
  13. that you could actually solve in polynomial time even before you fire up your search trees.
  14. So you're kind of nibbling away at your input here and what of course that means is
  15. if your pre-processing is successful then you do not need a search tree that is as big as the original input
  16. but maybe only a smaller one.
  17. So let me give you one concrete example for pre-processing now.
  18. And we're going to do this for SAT because SAT is actually a problem where
  19. pre-processing is heavily used.
  20. If you use a commercial software package to solve SAT,
  21. this package will rely heavily on pre-processing.
  22. I once talked to somebody who programs these packages and he says it's 90-95%
  23. pre-processing in most of the cases that leads their software to be able to solve SAT
  24. for large instances so even if you have 1000 variables or so.
  25. You'll remember that SAT was the problem for determining for a Boolean formula
  26. if that formula has a satisfying assignment or not.
  27. And I'm going to write down one Boolean formula for you here
  28. x₁ or x₃ and not x₁ and x₂ or not x₄ and not x₂ or not x₃ and x₁ and not x₁ or not x₂.
  29. Now of course to find out if this formula here has a satisfying assignment,
  30. you could play around with the variables.
  31. It's just four variables so not that many combinations.
  32. But for pre-processing of course you are trying to avoid that so what I would like you to do now
  33. in the next quiz is to look at this formula here and without trying different truth assignments
  34. find if there's one or two variables in here for which you can already say
  35. if they have to be set to be true or false in a satisfying assignment without trying different values.
  36. Is it x₁? x₂? x₃? x₄?
  37. Please make a check mark for those variables where you can easily see
  38. if they should be set to true or false without experimenting around with the values.
  39. And of course more than one can be true or none can be true. Check which ever one is correct.