ENCODING NP-COMPLETE PROBLEM INSTANCES INTO NATURAL LANGUAGE FOR LLM PROCESSING

Abstract

Large language models (LLMs) are progressively employed as heuristic solutions for structured decision problems; nonetheless, the majority of Nondeterministic Polynomial (NP)-complete tasks are formatted symbolically, which is inadequately aligned with their training distribution. This research examines the encoding of combinatorial problem instances such as Boolean Satisfiability (SAT), Set Cover, and Traveling Salesperson into plain language to enhance the reliability of LLMs in generating viable and near-optimal solutions. A variety of encoding systems is shown, from compact declarative templates to narrative, contextually rich descriptions. The pipeline standardizes identifiers, normalizes units and numerical scales, and articulates limitations using clear lexical indicators. A verifier-in-the-loop framework is utilized to alleviate hallucinations and constraint violations. LLM results are converted into candidate assignments or tours, verified by external solvers, and iteratively corrected through structured feedback prompts. Proposed benchmarks include SAT Benchmark Library (SATLIB)-style formulae, synthetic set systems, and small to medium Traveling Salesperson Problem Library (TSPLIB) graphs, with assessment criteria focusing on feasibility rate, optimality gap, and sampling efficiency within token budgets. Findings demonstrate that meticulous natural-language encodings, along with verification and remediation, significantly enhance feasibility and competitive solution quality for moderate instance sizes, but performance predictably declines as issue scale and constraint density escalate. The research offers pragmatic principles and reusable templates for converting symbolic NP-complete examples into a format comprehensible to LLMs, in addition to a comprehensive method for verifier-aware prompting.