Trong lĩnh vực lý thuyết độ phức tạp tính toán, ngôn ngữ và bài toán là những khái niệm có liên quan mật thiết với nhau. Lý thuyết độ phức tạp tính toán liên quan đến việc nghiên cứu các tài nguyên cần thiết để giải quyết các vấn đề tính toán và ngôn ngữ cung cấp một cách chính thức để mô tả các vấn đề này. Trong bối cảnh này, một ngôn ngữ là một tập hợp các chuỗi trên một bảng chữ cái nhất định, trong đó