COMP 992 Project Artifacts

Project Objective

This repository contains the implementation artifacts for the COMP 992 project:

Can LLMs Solve NP-Hard Problems?

The project evaluates how well modern large language models handle two NP-hard settings:

• Minimum Vertex Cover
• 3-SAT

The objective is to measure correctness, robustness, and failure modes across prompting strategies and model providers, then report results in paper-ready tables, figures, and appendix materials.

Methodology (Brief)

The workflow is consistent across both experiments:

1. Generate benchmark instances by difficulty category.
2. Compute ground truth solutions using deterministic algorithmic baselines.
3. Query LLMs with multiple prompting strategies.
4. Parse model outputs into structured predictions.
5. Compare predictions against ground truth.
6. Export aggregate metrics, plots, and appendix artifacts.

The experiments currently support two providers (Anthropic and OpenAI) and three prompt styles:

• zero_shot
• cot
• algo_guided

Repository Layout

• vertex_cover_experiment/vc_experiments: Vertex Cover pipeline
• sat_experiment/sat_experiments: 3-SAT pipeline
• Can_LLMs_Solve_NP_Hard_Problems(Paper): ACM paper source and appendix chapters

Prerequisites

• Python 3.10+ recommended
• API keys for both providers:
  • ANTHROPIC_API_KEY
  • OPENAI_API_KEY

Create a .env file in each experiment folder (or run from a shell where these vars are already set):

ANTHROPIC_API_KEY=your_anthropic_key OPENAI_API_KEY=your_openai_key

Optional model overrides:

CLAUDE_MODEL=claude-sonnet-4-6 OPENAI_MODEL=gpt-4o

Install Dependencies

Install dependencies separately for each artifact pipeline.

Vertex Cover

cd vertex_cover_experiment
python -m pip install -r requirements.txt

3-SAT

cd sat_experiment
python -m pip install -r requirements.txt

How To Run Artifacts

Each experiment has a master orchestrator that supports staged or full execution.

A) Vertex Cover Artifact

Run from vertex_cover_experiment/vc_experiments.

cd vertex_cover_experiment/vc_experiments

# Step 1: generate instances + ground truth
python main.py --setup

# Step 2: run LLM experiments
python main.py --run

# Step 3: analysis (tables + figures)
python main.py --analyze

# Step 4: export appendix assets
python main.py --appendix

# Full pipeline
python main.py --all

Useful options:

python main.py --status
python main.py --run --dry-run
python main.py --run --claude-only
python main.py --run --openai-only

Outputs:

• Raw responses: vertex_cover_experiment/vc_experiments/results/raw
• Processed results: vertex_cover_experiment/vc_experiments/results/processed
• Tables: vertex_cover_experiment/vc_experiments/results/tables
• Figures: vertex_cover_experiment/vc_experiments/results/figures
• Appendix exports: vertex_cover_experiment/vc_experiments/results/appendix

B) 3-SAT Artifact

Run from sat_experiment/sat_experiments.

cd sat_experiment/sat_experiments

# Step 1: generate instances + ground truth
python main_sat.py --setup

# Step 2: run LLM experiments
python main_sat.py --run

# Step 3: analysis (tables + figures)
python main_sat.py --analyze

# Step 4: export appendix assets
python main_sat.py --appendix

# Full pipeline
python main_sat.py --all

Useful options:

python main_sat.py --status
python main_sat.py --run --dry-run
python main_sat.py --run --claude-only
python main_sat.py --run --openai-only

Outputs:

• Raw responses: sat_experiment/sat_experiments/results_sat/raw
• Processed results: sat_experiment/sat_experiments/results_sat/processed
• Tables: sat_experiment/sat_experiments/results_sat/tables
• Figures: sat_experiment/sat_experiments/results_sat/figures
• Appendix exports: sat_experiment/sat_experiments/results_sat/appendix

Paper Artifact

The paper source is under Can_LLMs_Solve_NP_Hard_Problems(Paper).

Main manuscript file:

• main-paper.tex

Appendix chapter files are under:

• chapters/

If you have a LaTeX toolchain installed, compile from that directory using your preferred ACM-compatible workflow (for example latexmk).

Reproducibility Notes

• Default temperature is configured to 0.0 for deterministic sampling behavior where supported.
• API retries and delays are configurable in each experiment config.py.
• Generated outputs are organized so tables, figures, and appendices can be regenerated from pipeline stages.