On expressive power of regular realizability problems |
| |
Authors: | M N Vyalyi |
| |
Affiliation: | 1. Computing Center of the Russian Academy of Sciences, Moscow, Russia
|
| |
Abstract: | A regular realizability (RR) problem is a problem of testing nonemptiness of intersection of some fixed language (filter) with a regular language. We show that RR problems are universal in the following sense. For any language L there exists an RR problem equivalent to L under disjunctive reductions in nondeterministic log space. From this result, we derive existence of complete problems under polynomial reductions for many complexity classes, including all classes of the polynomial hierarchy. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|