Problems solvable in polynomial time

Proofs or statements that specific problems lie in P or L: graph reachability (PATH) with its marking machine, undirected connectivity in L, 2-SAT, primality, matching, maximum flow, linear programming, integer programming in fixed dimension, and hypergraph matching and cut questions.

• 2-satisfiability
• AKS primality test
• Graph reachability
• Hypergraph k-cut for fixed k
• Integer programming in fixed dimension
• Linear programming feasibility
• Matching in general graphs
• Maximum flow
• Perfect matchings in dense uniform hypergraphs
• Undirected s-t connectivity

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.