Karp: A Language for NP Reductions

8.12

Karp: A Language for NP Reductions🔗ℹ

Chenhao Zhang

Karp is a domain specific language for writing reductions between NP problems as programs and random-testing their correctness.

This documentation gives a tutorial-style guide to programming in Karp, followed by a description of its features and libraries. For details about the design rationale and the implementation of Karp, see "Karp: a language for NP reductions".

1 Getting Started with Karp, by Example

1.1 The Structure of Reductions in Karp

1.2 Problem Definitions

1.3 Reduction

1.3.1 Forward Certificate Construction

1.3.2 Backward Certificate Construction

1.3.3 Testing Reductions

3.1 Additional Operations

4 Structure Libraries

4.1 cnf

4.2 graph

4.3 mapping

1	Getting Started with Karp, by Example
2	Problem Definition
3	Reduction
4	Structure Libraries