How far can we go today?

• Arbitrary partial orders (nonlattices)

  • Minimal classification problem becomes NP-complete
    • Reduction from 3-SAT
    • Intuition: multiple upper bounds with no least upper bound leads to choice

Previous slide

Next slide

Back to first slide

View graphic version