zbMATH — the first resource for mathematics

Vector language: Simple description of hard instances. (English) Zbl 0733.68051
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?

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