Vector language: Simple description of hard instances. (English) Zbl 0733.68051

Kowaluk, Miroslaw; Wagner, Klaus W.

Mathematical foundations of computer science, Proc. 15th Symp., MFCS ’90, Banská Bystrica/Czech. 1990, Lect. Notes Comput. Sci. 452, 378-384 (1990).

Summary: [For the entire collection see Zbl 0731.00026.]
Different versions of vector languages are introduced as input languages for the succinct description of instances to combinatorial problems. For some of these languages we prove: (1) These languages are hard input languages, i.e. all popular non-trivial combinatorial problems have the maximum complexity blow-up if the instances are described by the language and (2) These languages are simpler than (i.e. there are simple compilers to) all other hard input languages investigated so far. To prove (1) we introduce different versions of vector-reducibilities which are restricted \(AC^ 0\) reducibilities. This investigation gives partial answers to the questions: How simple can hard instances to a combinatorial problem be? How simple can the reductions between the most popular combinatorial problems be?

MSC:

68Q45	Formal languages and automata
68R05	Combinatorics in computer science
68Q25	Analysis of algorithms and problem complexity

Keywords:

input languages; combinatorial problems; vector-reducibilities