NP Reduction Visualizer

A Python-based interactive visualizer for NP-complete problem reductions. This tool provides dynamic visualizations of problem instances and their corresponding reductions, such as 3SAT → Independent Set and 3SAT → 3-Coloring. For detailed documentation, see Documentation.pdf in the repository.

📦 Installation

Requirements

• Python 3
• numpy
• pygame

Clone the Repository

git clone git@github.com:wuwendyy/NP-reduction-visualization.git
cd NP-reduction-visualization

(Optional) Setup with Anaconda

conda create -n npvis python=3.12
conda activate npvis

Install Dependencies

pip install -e .

🚀 Running Example Programs

3SAT → Independent Set

Run:

python -m tests.reduction_test.test_3sat_to_is

A window will open showing:

• Left: 3SAT problem
• Right: Independent Set problem

Clicking an element in either panel highlights corresponding elements in the other. Press S to toggle solution visualization using color groups.

---

3SAT → 3Coloring

Run:

python -m tests.reduction_test.test_3sat_to_3color

This visualizer allows multiple elements in the 3Color panel to correspond to one 3SAT clause. The more elements you select, the brighter the clause's highlight.

3 Elements Selected	6 Elements Selected

---

🧩 Core Classes

Element and SubElement

• Element: Abstract class with methods parse(), display(), and handle_event().
• SubElement: Abstract class used for core visual components such as nodes, edges, variables, and clauses.

Node:

node.py

Basic Node for a graph

Edge

edge.py

Connects two nodes with highlighting behavior.

Variable and Clause

variable.py and clause.py

Used in SAT formulas, supporting logical evaluation and color-based visualization.

---

Graph

graph.py || sample usage

Encapsulates visual representation of nodes and edges. Supports grouped node layouts and collision avoidance.

Input Format (TXT):

X1
X2
...
(X1, X2)
...
[X1, X2, X4]

Random Graph	Grouped Graph

---

Formula

formula.py || sample usage

Represents a 3SAT-style Boolean formula with text parsing and rendering.

Input Format:

• Literal expressions like X1 OR NOT X2 OR X3 in specific syntax.

Basic	Colored

---

🔍 NP_Problem Classes

IndependentSetProblem

independent_set.py

Given a graph, verify if selected nodes form a valid independent set (no two connected). Supports evaluation and visual feedback.

Default	With Solution

---

for usage example:

ThreeSATProblem

three_sat.py

Evaluates whether a Boolean formula with 3-literal clauses can be satisfied.

---

🛠 Development Notes

• Core visual logic powered by Pygame
• Modular architecture with reusable Element types
• Input files and visual styling defined clearly for extensibility