NP-Completeness Investigation of a Scheduling Feature Request
Overview
What this challenge is about.
Read the feature spec (around 30 vets per clinic, around 10 rooms, around 200 appointments per day, vet-skill constraints, room-equipment constraints, customer-time preferences). Show the formal reduction from the feature to a known NP-hard problem (likely candidates: list-coloring, generalized assignment, or job-shop scheduling). If it isn't NP-hard, prove why with a polynomial algorithm sketch. Survey 3 real solver options (CP-SAT via OR-Tools, MILP via PuLP, a custom heuristic) and recommend which to ship — including 'don't ship optimal, ship good-enough heuristic with a manual-override' as a real option. Deliver a 6-page recommendation memo.
The Brief
What you'll do, and what you'll demonstrate.
Determine whether the requested optimal-scheduling feature is NP-hard and recommend a tractable shipping path.
Earning criteria — what you'll demonstrate
- Recognize NP-hard problems hiding in product feature requests
- Write a formal reduction from a real problem to a known NP-complete problem
- Survey practical solvers and choose one defensibly
- Communicate complexity trade-offs to non-CS stakeholders
Program Fit
Where this fits in your program.
Sharpens the same skills your degree expects you to demonstrate.
Skills
Skills you'll demonstrate.
Each one shows up on your verified credential.
Careers
Roles this prepares you for.
Real titles. Real skill bridges. Pick the one closest to your trajectory.
Product Manager
Technically literate product managers who understand NP-hardness can negotiate scope intelligently with customers instead of overpromising.
This challenge sharpens
- stakeholder-communication
- research
- constraint-handling