An interactive, dynamic knowledgebase of canonical Computer Science problems, solutions, and reductions
- Website: https://redux.portneuf.cose.isu.edu/
- API Documentation: https://api.redux.portneuf.cose.isu.edu/swagger/index.html
- About Redux
- Quick Start
- Architecture
- Contributing
- Production Deployment
- Contributors
- Additional Resources
- License
- Contact & Support
Redux is an extensible, interactive web-based platform designed for Computer Science pedagogy. It provides:
- Interactive Problem Visualization: Explore problems across complexity classes, from P to NP-Hard and beyond
- Reduction Framework: Understand how problems reduce to one another
- Solver & Verifier Tools: Execute and verify solutions to computational problems
- Educational Resource: Built on Karp's 21 NP-Complete problems and expanded across multiple complexity classes
The backend is designed to be adaptable and can work with different frontends. The default frontend can be found at Redux_GUI.
Full instructions, including forking, Docker, and the dev container, are in the setup guide. The short version:
-
Install the .NET 10 SDK (and Node.js only if you also want to run the frontend).
-
Clone the repo and run the API from the repo root:
git clone https://github.com/ReduxISU/Redux.git cd Redux dotnet runThe API listens on
http://127.0.0.1:27000/. -
Open Swagger, the interactive API page, at
http://127.0.0.1:27000/swagger/index.html.
For automatic reloading while you edit, use dotnet watch --project API.csproj run. To run the Docker image, use docker build -t reduxapi . and then docker run -it --rm -p 27000:27000 --name reduxapi reduxapi.
Redux has five kinds of building blocks. Each one is a C# class that implements an interface from the Interfaces/ folder, and the API finds them automatically (no controllers to write):
- IProblem: a problem, with its definition and default example
- ISolver: solves a problem instance
- IVerifier: checks whether an answer (a certificate) is correct
- IVisualization: turns a problem into a picture the frontend can draw
- IReduction: turns an instance of one problem into an instance of another
Redux/
├── Problems/
│ ├── NPComplete/ # NPC_<NAME>/ folders: the main problem set
│ ├── NPHard/ # NPH_<NAME>/
│ └── P/ # P_<NAME>/
│ └── each problem has <NAME>_Class.cs, Solvers/, Verifiers/,
│ Visualizations/, and ReduceTo/NPC_<TO>/ (reductions)
├── Interfaces/ # The five interfaces, enums, and graph utilities
├── AdditionalControllers/ # ProblemProvider and Navigation/ (API endpoints)
├── ProblemTemplate/ # Starter-file templates
├── redux-tests/ # Tests
└── API.csproj # Main project file
The Navigation controllers in AdditionalControllers/Navigation/ are heavily used by the frontend, so change them carefully. The how the code works guide explains the folders, the interfaces, graph utilities, the SPADE instance parser, and the Navigation controllers.
We welcome contributions! Start with the contributor guides, which cover setup, how the code works, building and testing, and step-by-step guides for adding a problem, solver, verifier, reduction, or visualization. CONTRIBUTING.md has the license terms and the pull request workflow.
In short: fork the repo, make a branch, open a pull request to the CSharpAPI branch, and wait for review before merging.
Join the community on Discord: https://discord.gg/sEC3rTXn2Z
How the live server is run, restarted, and updated is documented in Documentation/production.md.
This project is developed by students and faculty at Idaho State University's Computer Science Department.
For a complete list of contributors, visit our About Us page.
- GitHub Repository
- Contributor guides
- Wikipedia: What is NP-Complete?
- Karp's 21 NP-Complete Problems
- Redux GUI Documentation
- SPADE Parser
- Frontend: Redux_GUI
- Quantum Solver: quantumsolver
This project is licensed under the BSD 3-Clause License. See LICENSE for details.
- Issues: Please use GitHub Issues for bug reports and feature requests
- Discord: Join our community
- Email: Contact the Redux team at redux@isu.edu